| // 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/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."); |
| DEFINE_FLAG(bool, trace_constant_propagation, false, |
| "Print constant propagation and useless code elimination."); |
| DEFINE_FLAG(bool, trace_optimization, false, "Print optimization details."); |
| DEFINE_FLAG(bool, trace_range_analysis, false, "Trace range analysis progress"); |
| DEFINE_FLAG(bool, truncating_left_shift, true, |
| "Optimize left shift to truncate if possible"); |
| DEFINE_FLAG(bool, use_cha, true, "Use class hierarchy analysis."); |
| DECLARE_FLAG(bool, eliminate_type_checks); |
| DECLARE_FLAG(bool, enable_type_checks); |
| DECLARE_FLAG(bool, trace_type_check_elimination); |
| |
| |
| |
| // Optimize instance calls using ICData. |
| void FlowGraphOptimizer::ApplyICData() { |
| VisitBlocks(); |
| } |
| |
| |
| // Optimize instance calls using cid. |
| // Attempts to convert an instance call (IC call) using propagated class-ids, |
| // e.g., receiver class id, guarded-cid. |
| void FlowGraphOptimizer::ApplyClassIds() { |
| ASSERT(current_iterator_ == NULL); |
| for (intptr_t i = 0; i < block_order_.length(); ++i) { |
| BlockEntryInstr* entry = block_order_[i]; |
| ForwardInstructionIterator it(entry); |
| current_iterator_ = ⁢ |
| for (; !it.Done(); it.Advance()) { |
| Instruction* instr = it.Current(); |
| if (instr->IsInstanceCall()) { |
| InstanceCallInstr* call = instr->AsInstanceCall(); |
| if (call->HasICData()) { |
| if (TryCreateICData(call)) { |
| VisitInstanceCall(call); |
| } |
| } |
| } else if (instr->IsPolymorphicInstanceCall()) { |
| SpecializePolymorphicInstanceCall(instr->AsPolymorphicInstanceCall()); |
| } else if (instr->IsStrictCompare()) { |
| VisitStrictCompare(instr->AsStrictCompare()); |
| } else if (instr->IsBranch()) { |
| ComparisonInstr* compare = instr->AsBranch()->comparison(); |
| if (compare->IsStrictCompare()) { |
| VisitStrictCompare(compare->AsStrictCompare()); |
| } else if (compare->IsEqualityCompare()) { |
| StrictifyEqualityCompare(compare->AsEqualityCompare(), |
| instr->AsBranch()); |
| } |
| } |
| } |
| current_iterator_ = NULL; |
| } |
| } |
| |
| |
| // Attempt to build ICData for call using propagated class-ids. |
| bool FlowGraphOptimizer::TryCreateICData(InstanceCallInstr* call) { |
| ASSERT(call->HasICData()); |
| if (call->ic_data()->NumberOfChecks() > 0) { |
| // This occurs when an instance call has too many checks. |
| // TODO(srdjan): Replace IC call with megamorphic call. |
| return false; |
| } |
| 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->PushArgumentAt(i)->value()->Type()->ToCid(); |
| class_ids.Add(cid); |
| } |
| // TODO(srdjan): Test for number of arguments checked greater than 1. |
| if (class_ids.length() != 1) { |
| return false; |
| } |
| if (class_ids[0] != kDynamicCid) { |
| const intptr_t num_named_arguments = call->argument_names().IsNull() ? |
| 0 : call->argument_names().Length(); |
| const Class& receiver_class = Class::Handle( |
| Isolate::Current()->class_table()->At(class_ids[0])); |
| Function& function = Function::Handle(); |
| function = Resolver::ResolveDynamicForReceiverClass( |
| receiver_class, |
| call->function_name(), |
| call->ArgumentCount(), |
| num_named_arguments); |
| if (function.IsNull()) { |
| return false; |
| } |
| // Create new ICData, do not modify the one attached to the instruction |
| // since it is attached to the assembly instruction itself. |
| // TODO(srdjan): Prevent modification of ICData object that is |
| // referenced in assembly code. |
| ICData& ic_data = ICData::ZoneHandle(ICData::New( |
| flow_graph_->parsed_function().function(), |
| call->function_name(), |
| call->deopt_id(), |
| class_ids.length())); |
| ic_data.AddReceiverCheck(class_ids[0], function); |
| call->set_ic_data(&ic_data); |
| return true; |
| } |
| return false; |
| } |
| |
| |
| static const ICData& SpecializeICData(const ICData& ic_data, intptr_t cid) { |
| ASSERT(ic_data.num_args_tested() == 1); |
| |
| if ((ic_data.NumberOfChecks() == 1) && |
| (ic_data.GetReceiverClassIdAt(0) == cid)) { |
| return ic_data; // Nothing to do |
| } |
| |
| const ICData& new_ic_data = ICData::ZoneHandle(ICData::New( |
| Function::Handle(ic_data.function()), |
| String::Handle(ic_data.target_name()), |
| ic_data.deopt_id(), |
| ic_data.num_args_tested())); |
| |
| const Function& function = |
| Function::Handle(ic_data.GetTargetForReceiverClassId(cid)); |
| if (!function.IsNull()) { |
| new_ic_data.AddReceiverCheck(cid, function); |
| } |
| |
| return new_ic_data; |
| } |
| |
| |
| void FlowGraphOptimizer::SpecializePolymorphicInstanceCall( |
| PolymorphicInstanceCallInstr* call) { |
| if (!call->with_checks()) { |
| return; // Already specialized. |
| } |
| |
| const intptr_t receiver_cid = |
| call->PushArgumentAt(0)->value()->Type()->ToCid(); |
| if (receiver_cid == kDynamicCid) { |
| return; // No information about receiver was infered. |
| } |
| |
| const ICData& ic_data = SpecializeICData(call->ic_data(), receiver_cid); |
| |
| const bool with_checks = false; |
| PolymorphicInstanceCallInstr* specialized = |
| new PolymorphicInstanceCallInstr(call->instance_call(), |
| ic_data, |
| with_checks); |
| call->ReplaceWith(specialized, current_iterator()); |
| } |
| |
| |
| static BinarySmiOpInstr* AsSmiShiftLeftInstruction(Definition* d) { |
| BinarySmiOpInstr* instr = d->AsBinarySmiOp(); |
| if ((instr != NULL) && (instr->op_kind() == Token::kSHL)) { |
| return instr; |
| } |
| return NULL; |
| } |
| |
| |
| static bool IsPositiveOrZeroSmiConst(Definition* d) { |
| ConstantInstr* const_instr = d->AsConstant(); |
| if ((const_instr != NULL) && (const_instr->value().IsSmi())) { |
| return Smi::Cast(const_instr->value()).Value() >= 0; |
| } |
| return false; |
| } |
| |
| |
| void FlowGraphOptimizer::OptimizeLeftShiftBitAndSmiOp( |
| Definition* bit_and_instr, |
| Definition* left_instr, |
| Definition* right_instr) { |
| ASSERT(bit_and_instr != NULL); |
| ASSERT((left_instr != NULL) && (right_instr != NULL)); |
| |
| // Check for pattern, smi_shift_left must be single-use. |
| bool is_positive_or_zero = IsPositiveOrZeroSmiConst(left_instr); |
| if (!is_positive_or_zero) { |
| is_positive_or_zero = IsPositiveOrZeroSmiConst(right_instr); |
| } |
| if (!is_positive_or_zero) return; |
| |
| BinarySmiOpInstr* smi_shift_left = NULL; |
| if (bit_and_instr->InputAt(0)->IsSingleUse()) { |
| smi_shift_left = AsSmiShiftLeftInstruction(left_instr); |
| } |
| if ((smi_shift_left == NULL) && (bit_and_instr->InputAt(1)->IsSingleUse())) { |
| smi_shift_left = AsSmiShiftLeftInstruction(right_instr); |
| } |
| if (smi_shift_left == NULL) return; |
| |
| // Pattern recognized. |
| smi_shift_left->set_is_truncating(true); |
| ASSERT(bit_and_instr->IsBinarySmiOp() || bit_and_instr->IsBinaryMintOp()); |
| if (bit_and_instr->IsBinaryMintOp()) { |
| // Replace Mint op with Smi op. |
| BinarySmiOpInstr* smi_op = new BinarySmiOpInstr( |
| Token::kBIT_AND, |
| bit_and_instr->AsBinaryMintOp()->instance_call(), |
| new Value(left_instr), |
| new Value(right_instr)); |
| bit_and_instr->ReplaceWith(smi_op, current_iterator()); |
| } |
| } |
| |
| |
| // Optimize (a << b) & c pattern: if c is a positive Smi or zero, then the |
| // shift can be a truncating Smi shift-left and result is always Smi. |
| void FlowGraphOptimizer::TryOptimizeLeftShiftWithBitAndPattern() { |
| if (!FLAG_truncating_left_shift) return; |
| ASSERT(current_iterator_ == NULL); |
| for (intptr_t i = 0; i < block_order_.length(); ++i) { |
| BlockEntryInstr* entry = block_order_[i]; |
| ForwardInstructionIterator it(entry); |
| current_iterator_ = ⁢ |
| for (; !it.Done(); it.Advance()) { |
| if (it.Current()->IsBinarySmiOp()) { |
| BinarySmiOpInstr* binop = it.Current()->AsBinarySmiOp(); |
| if (binop->op_kind() == Token::kBIT_AND) { |
| OptimizeLeftShiftBitAndSmiOp(binop, |
| binop->left()->definition(), |
| binop->right()->definition()); |
| } |
| } else if (it.Current()->IsBinaryMintOp()) { |
| BinaryMintOpInstr* mintop = it.Current()->AsBinaryMintOp(); |
| if (mintop->op_kind() == Token::kBIT_AND) { |
| OptimizeLeftShiftBitAndSmiOp(mintop, |
| mintop->left()->definition(), |
| mintop->right()->definition()); |
| } |
| } |
| } |
| current_iterator_ = NULL; |
| } |
| } |
| |
| |
| static void EnsureSSATempIndex(FlowGraph* graph, |
| Definition* defn, |
| Definition* replacement) { |
| if ((replacement->ssa_temp_index() == -1) && |
| (defn->ssa_temp_index() != -1)) { |
| replacement->set_ssa_temp_index(graph->alloc_ssa_temp_index()); |
| } |
| } |
| |
| |
| static void ReplaceCurrentInstruction(ForwardInstructionIterator* iterator, |
| Instruction* current, |
| Instruction* replacement, |
| FlowGraph* graph) { |
| Definition* current_defn = current->AsDefinition(); |
| if ((replacement != NULL) && (current_defn != NULL)) { |
| Definition* replacement_defn = replacement->AsDefinition(); |
| ASSERT(replacement_defn != NULL); |
| current_defn->ReplaceUsesWith(replacement_defn); |
| EnsureSSATempIndex(graph, current_defn, replacement_defn); |
| |
| if (FLAG_trace_optimization) { |
| OS::Print("Replacing v%"Pd" with v%"Pd"\n", |
| current_defn->ssa_temp_index(), |
| replacement_defn->ssa_temp_index()); |
| } |
| } else if (FLAG_trace_optimization) { |
| if (current_defn == NULL) { |
| OS::Print("Removing %s\n", current->DebugName()); |
| } else { |
| ASSERT(!current_defn->HasUses()); |
| OS::Print("Removing v%"Pd".\n", current_defn->ssa_temp_index()); |
| } |
| } |
| iterator->RemoveCurrentFromGraph(); |
| } |
| |
| |
| void FlowGraphOptimizer::Canonicalize() { |
| for (intptr_t i = 0; i < block_order_.length(); ++i) { |
| BlockEntryInstr* entry = block_order_[i]; |
| entry->Accept(this); |
| for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) { |
| Instruction* current = it.Current(); |
| Instruction* replacement = current->Canonicalize(this); |
| if (replacement != current) { |
| // For non-definitions Canonicalize should return either NULL or |
| // this. |
| ASSERT((replacement == NULL) || current->IsDefinition()); |
| ReplaceCurrentInstruction(&it, current, replacement, flow_graph_); |
| } |
| } |
| } |
| } |
| |
| |
| void FlowGraphOptimizer::InsertConversion(Representation from, |
| Representation to, |
| Value* use, |
| Instruction* insert_before, |
| Instruction* deopt_target) { |
| Definition* converted = NULL; |
| if ((from == kTagged) && (to == kUnboxedMint)) { |
| ASSERT((deopt_target != NULL) || |
| (use->Type()->ToCid() == kDoubleCid)); |
| const intptr_t deopt_id = (deopt_target != NULL) ? |
| deopt_target->DeoptimizationTarget() : Isolate::kNoDeoptId; |
| converted = new UnboxIntegerInstr(use->CopyWithType(), deopt_id); |
| |
| } else if ((from == kUnboxedMint) && (to == kTagged)) { |
| converted = new BoxIntegerInstr(use->CopyWithType()); |
| |
| } else if (from == kUnboxedMint && to == kUnboxedDouble) { |
| // Convert by boxing/unboxing. |
| // TODO(fschneider): Implement direct unboxed mint-to-double conversion. |
| BoxIntegerInstr* boxed = new BoxIntegerInstr(use->CopyWithType()); |
| use->BindTo(boxed); |
| InsertBefore(insert_before, boxed, NULL, Definition::kValue); |
| |
| const intptr_t deopt_id = (deopt_target != NULL) ? |
| deopt_target->DeoptimizationTarget() : Isolate::kNoDeoptId; |
| converted = new UnboxDoubleInstr(new Value(boxed), deopt_id); |
| |
| } else if ((from == kUnboxedDouble) && (to == kTagged)) { |
| converted = new BoxDoubleInstr(use->CopyWithType()); |
| |
| } else if ((from == kTagged) && (to == kUnboxedDouble)) { |
| ASSERT((deopt_target != NULL) || |
| (use->Type()->ToCid() == kDoubleCid)); |
| const intptr_t deopt_id = (deopt_target != NULL) ? |
| deopt_target->DeoptimizationTarget() : Isolate::kNoDeoptId; |
| ConstantInstr* constant = use->definition()->AsConstant(); |
| if ((constant != NULL) && constant->value().IsSmi()) { |
| const double dbl_val = Smi::Cast(constant->value()).AsDoubleValue(); |
| const Double& dbl_obj = |
| Double::ZoneHandle(Double::New(dbl_val, Heap::kOld)); |
| ConstantInstr* double_const = new ConstantInstr(dbl_obj); |
| InsertBefore(insert_before, double_const, NULL, Definition::kValue); |
| converted = new UnboxDoubleInstr(new Value(double_const), deopt_id); |
| } else { |
| converted = new UnboxDoubleInstr(use->CopyWithType(), deopt_id); |
| } |
| } else if ((from == kTagged) && (to == kUnboxedFloat32x4)) { |
| ASSERT((deopt_target != NULL) || |
| (use->Type()->ToCid() == kFloat32x4Cid)); |
| const intptr_t deopt_id = (deopt_target != NULL) ? |
| deopt_target->DeoptimizationTarget() : Isolate::kNoDeoptId; |
| converted = new UnboxFloat32x4Instr(use->CopyWithType(), deopt_id); |
| } else if ((from == kUnboxedFloat32x4) && (to == kTagged)) { |
| converted = new BoxFloat32x4Instr(use->CopyWithType()); |
| } else if ((from == kTagged) && (to == kUnboxedUint32x4)) { |
| ASSERT((deopt_target != NULL) || (use->Type()->ToCid() == kUint32x4Cid)); |
| const intptr_t deopt_id = (deopt_target != NULL) ? |
| deopt_target->DeoptimizationTarget() : Isolate::kNoDeoptId; |
| converted = new UnboxUint32x4Instr(use->CopyWithType(), deopt_id); |
| } else if ((from == kUnboxedUint32x4) && (to == kTagged)) { |
| converted = new BoxUint32x4Instr(use->CopyWithType()); |
| } |
| ASSERT(converted != NULL); |
| use->BindTo(converted); |
| InsertBefore(insert_before, converted, use->instruction()->env(), |
| Definition::kValue); |
| } |
| |
| |
| void FlowGraphOptimizer::InsertConversionsFor(Definition* def) { |
| const Representation from_rep = def->representation(); |
| |
| for (Value::Iterator it(def->input_use_list()); |
| !it.Done(); |
| it.Advance()) { |
| Value* use = it.Current(); |
| const Representation to_rep = |
| use->instruction()->RequiredInputRepresentation(use->use_index()); |
| if (from_rep == to_rep || to_rep == kNoRepresentation) { |
| continue; |
| } |
| |
| Instruction* insert_before; |
| Instruction* deopt_target; |
| PhiInstr* phi = use->instruction()->AsPhi(); |
| if (phi != NULL) { |
| ASSERT(phi->is_alive()); |
| // For phis conversions have to be inserted in the predecessor. |
| insert_before = |
| phi->block()->PredecessorAt(use->use_index())->last_instruction(); |
| deopt_target = NULL; |
| } else { |
| deopt_target = insert_before = use->instruction(); |
| } |
| |
| InsertConversion(from_rep, to_rep, use, insert_before, deopt_target); |
| } |
| } |
| |
| |
| void FlowGraphOptimizer::SelectRepresentations() { |
| // Convervatively unbox all phis that were proven to be of type Double. |
| for (intptr_t i = 0; i < block_order_.length(); ++i) { |
| JoinEntryInstr* join_entry = block_order_[i]->AsJoinEntry(); |
| if (join_entry != NULL) { |
| for (PhiIterator it(join_entry); !it.Done(); it.Advance()) { |
| PhiInstr* phi = it.Current(); |
| ASSERT(phi != NULL); |
| if (phi->Type()->ToCid() == kDoubleCid) { |
| phi->set_representation(kUnboxedDouble); |
| } |
| } |
| } |
| } |
| |
| // Process all instructions and insert conversions where needed. |
| GraphEntryInstr* graph_entry = block_order_[0]->AsGraphEntry(); |
| |
| // Visit incoming parameters and constants. |
| for (intptr_t i = 0; i < graph_entry->initial_definitions()->length(); i++) { |
| InsertConversionsFor((*graph_entry->initial_definitions())[i]); |
| } |
| |
| for (intptr_t i = 0; i < block_order_.length(); ++i) { |
| 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); |
| } |
| } |
| for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) { |
| Definition* def = it.Current()->AsDefinition(); |
| if (def != NULL) { |
| InsertConversionsFor(def); |
| } |
| } |
| } |
| } |
| |
| |
| static bool ICDataHasReceiverArgumentClassIds(const ICData& ic_data, |
| intptr_t receiver_class_id, |
| intptr_t argument_class_id) { |
| ASSERT(receiver_class_id != kIllegalCid); |
| ASSERT(argument_class_id != kIllegalCid); |
| if (ic_data.num_args_tested() != 2) return false; |
| |
| Function& target = Function::Handle(); |
| const intptr_t len = ic_data.NumberOfChecks(); |
| for (intptr_t i = 0; i < len; i++) { |
| GrowableArray<intptr_t> class_ids; |
| ic_data.GetCheckAt(i, &class_ids, &target); |
| ASSERT(class_ids.length() == 2); |
| if ((class_ids[0] == receiver_class_id) && |
| (class_ids[1] == argument_class_id)) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| |
| static bool ClassIdIsOneOf(intptr_t class_id, |
| const GrowableArray<intptr_t>& class_ids) { |
| for (intptr_t i = 0; i < class_ids.length(); i++) { |
| if (class_ids[i] == class_id) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| |
| // Returns true if ICData tests two arguments and all ICData cids are in the |
| // required sets 'receiver_class_ids' or 'argument_class_ids', respectively. |
| static bool ICDataHasOnlyReceiverArgumentClassIds( |
| const ICData& ic_data, |
| const GrowableArray<intptr_t>& receiver_class_ids, |
| const GrowableArray<intptr_t>& argument_class_ids) { |
| if (ic_data.num_args_tested() != 2) return false; |
| Function& target = Function::Handle(); |
| const intptr_t len = ic_data.NumberOfChecks(); |
| for (intptr_t i = 0; i < len; i++) { |
| GrowableArray<intptr_t> class_ids; |
| ic_data.GetCheckAt(i, &class_ids, &target); |
| ASSERT(class_ids.length() == 2); |
| if (!ClassIdIsOneOf(class_ids[0], receiver_class_ids) || |
| !ClassIdIsOneOf(class_ids[1], argument_class_ids)) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| |
| static bool HasOnlyOneSmi(const ICData& ic_data) { |
| return (ic_data.NumberOfChecks() == 1) |
| && ic_data.HasReceiverClassId(kSmiCid); |
| } |
| |
| |
| static bool HasOnlySmiOrMint(const ICData& ic_data) { |
| if (ic_data.NumberOfChecks() == 1) { |
| return ic_data.HasReceiverClassId(kSmiCid) |
| || ic_data.HasReceiverClassId(kMintCid); |
| } |
| return (ic_data.NumberOfChecks() == 2) |
| && ic_data.HasReceiverClassId(kSmiCid) |
| && ic_data.HasReceiverClassId(kMintCid); |
| } |
| |
| |
| static bool HasOnlyTwoSmis(const ICData& ic_data) { |
| return (ic_data.NumberOfChecks() == 1) && |
| ICDataHasReceiverArgumentClassIds(ic_data, kSmiCid, kSmiCid); |
| } |
| |
| static bool HasOnlyTwoFloat32x4s(const ICData& ic_data) { |
| return (ic_data.NumberOfChecks() == 1) && |
| ICDataHasReceiverArgumentClassIds(ic_data, kFloat32x4Cid, kFloat32x4Cid); |
| } |
| |
| |
| // Returns false if the ICData contains anything other than the 4 combinations |
| // of Mint and Smi for the receiver and argument classes. |
| static bool HasTwoMintOrSmi(const ICData& ic_data) { |
| GrowableArray<intptr_t> class_ids(2); |
| class_ids.Add(kSmiCid); |
| class_ids.Add(kMintCid); |
| return ICDataHasOnlyReceiverArgumentClassIds(ic_data, class_ids, class_ids); |
| } |
| |
| |
| static bool HasOnlyOneDouble(const ICData& ic_data) { |
| return (ic_data.NumberOfChecks() == 1) |
| && ic_data.HasReceiverClassId(kDoubleCid); |
| } |
| |
| |
| static bool ShouldSpecializeForDouble(const ICData& ic_data) { |
| // Unboxed double operation can't handle case of two smis. |
| if (ICDataHasReceiverArgumentClassIds(ic_data, kSmiCid, kSmiCid)) { |
| return false; |
| } |
| |
| // Check that it have seen only smis and doubles. |
| GrowableArray<intptr_t> class_ids(2); |
| class_ids.Add(kSmiCid); |
| class_ids.Add(kDoubleCid); |
| return ICDataHasOnlyReceiverArgumentClassIds(ic_data, class_ids, class_ids); |
| } |
| |
| |
| void FlowGraphOptimizer::ReplaceCall(Definition* call, |
| Definition* replacement) { |
| // Remove the original push arguments. |
| for (intptr_t i = 0; i < call->ArgumentCount(); ++i) { |
| PushArgumentInstr* push = call->PushArgumentAt(i); |
| push->ReplaceUsesWith(push->value()->definition()); |
| push->RemoveFromGraph(); |
| } |
| call->ReplaceWith(replacement, current_iterator()); |
| } |
| |
| |
| static intptr_t ReceiverClassId(InstanceCallInstr* call) { |
| if (!call->HasICData()) return kIllegalCid; |
| |
| const ICData& ic_data = ICData::Handle(call->ic_data()->AsUnaryClassChecks()); |
| |
| if (ic_data.NumberOfChecks() == 0) return kIllegalCid; |
| // TODO(vegorov): Add multiple receiver type support. |
| if (ic_data.NumberOfChecks() != 1) return kIllegalCid; |
| ASSERT(ic_data.HasOneTarget()); |
| |
| Function& target = Function::Handle(); |
| intptr_t class_id; |
| ic_data.GetOneClassCheckAt(0, &class_id, &target); |
| return class_id; |
| } |
| |
| |
| void FlowGraphOptimizer::AddCheckSmi(Definition* to_check, |
| intptr_t deopt_id, |
| Environment* deopt_environment, |
| Instruction* insert_before) { |
| if (to_check->Type()->ToCid() != kSmiCid) { |
| InsertBefore(insert_before, |
| new CheckSmiInstr(new Value(to_check), deopt_id), |
| deopt_environment, |
| Definition::kEffect); |
| } |
| } |
| |
| |
| void FlowGraphOptimizer::AddCheckClass(Definition* to_check, |
| const ICData& unary_checks, |
| intptr_t deopt_id, |
| Environment* deopt_environment, |
| Instruction* insert_before) { |
| // Type propagation has not run yet, we cannot eliminate the check. |
| Instruction* check = NULL; |
| if ((unary_checks.NumberOfChecks() == 1) && |
| (unary_checks.GetReceiverClassIdAt(0) == kSmiCid)) { |
| check = new CheckSmiInstr(new Value(to_check), deopt_id); |
| } else { |
| check = new CheckClassInstr(new Value(to_check), deopt_id, unary_checks); |
| } |
| InsertBefore(insert_before, check, deopt_environment, Definition::kEffect); |
| } |
| |
| |
| void FlowGraphOptimizer::AddReceiverCheck(InstanceCallInstr* call) { |
| AddCheckClass(call->ArgumentAt(0), |
| ICData::ZoneHandle(call->ic_data()->AsUnaryClassChecks()), |
| call->deopt_id(), |
| call->env(), |
| call); |
| } |
| |
| |
| static bool ArgIsAlwaysSmi(const ICData& ic_data, intptr_t arg_n) { |
| ASSERT(ic_data.num_args_tested() > arg_n); |
| if (ic_data.NumberOfChecks() == 0) return false; |
| GrowableArray<intptr_t> class_ids; |
| Function& target = Function::Handle(); |
| const intptr_t len = ic_data.NumberOfChecks(); |
| for (intptr_t i = 0; i < len; i++) { |
| ic_data.GetCheckAt(i, &class_ids, &target); |
| if (class_ids[arg_n] != kSmiCid) return false; |
| } |
| return true; |
| } |
| |
| |
| // Returns array classid to load from, array and index value |
| |
| intptr_t FlowGraphOptimizer::PrepareIndexedOp(InstanceCallInstr* call, |
| intptr_t class_id, |
| Definition** array, |
| Definition** index) { |
| // Insert class check and index smi checks and attach a copy of the |
| // original environment because the operation can still deoptimize. |
| AddReceiverCheck(call); |
| InsertBefore(call, |
| new CheckSmiInstr(new Value(*index), call->deopt_id()), |
| call->env(), |
| Definition::kEffect); |
| |
| // If both index and array are constants, then do a compile-time check. |
| // TODO(srdjan): Remove once constant propagation handles bounds checks. |
| bool skip_check = false; |
| if ((*array)->IsConstant() && (*index)->IsConstant()) { |
| const ImmutableArray& constant_array = |
| ImmutableArray::Cast((*array)->AsConstant()->value()); |
| const Object& constant_index = (*index)->AsConstant()->value(); |
| skip_check = constant_index.IsSmi() && |
| (Smi::Cast(constant_index).Value() < constant_array.Length()); |
| } |
| if (!skip_check) { |
| // Insert array length load and bounds check. |
| const bool is_immutable = |
| CheckArrayBoundInstr::IsFixedLengthArrayType(class_id); |
| LoadFieldInstr* length = |
| new LoadFieldInstr(new Value(*array), |
| CheckArrayBoundInstr::LengthOffsetFor(class_id), |
| Type::ZoneHandle(Type::SmiType()), |
| is_immutable); |
| length->set_result_cid(kSmiCid); |
| length->set_recognized_kind( |
| LoadFieldInstr::RecognizedKindFromArrayCid(class_id)); |
| InsertBefore(call, length, NULL, Definition::kValue); |
| |
| InsertBefore(call, |
| new CheckArrayBoundInstr(new Value(length), |
| new Value(*index), |
| class_id, |
| call), |
| call->env(), |
| Definition::kEffect); |
| } |
| if (class_id == kGrowableObjectArrayCid) { |
| // Insert data elements load. |
| LoadFieldInstr* elements = |
| new LoadFieldInstr(new Value(*array), |
| GrowableObjectArray::data_offset(), |
| Type::ZoneHandle(Type::DynamicType())); |
| elements->set_result_cid(kArrayCid); |
| InsertBefore(call, elements, NULL, Definition::kValue); |
| *array = elements; |
| return kArrayCid; |
| } |
| if (RawObject::IsExternalTypedDataClassId(class_id)) { |
| LoadUntaggedInstr* elements = |
| new LoadUntaggedInstr(new Value(*array), |
| ExternalTypedData::data_offset()); |
| InsertBefore(call, elements, NULL, Definition::kValue); |
| *array = elements; |
| } |
| return class_id; |
| } |
| |
| |
| static bool CanUnboxInt32() { |
| // Int32/Uint32 can be unboxed if it fits into a smi or the platform |
| // supports unboxed mints. |
| return (kSmiBits >= 32) || FlowGraphCompiler::SupportsUnboxedMints(); |
| } |
| |
| |
| bool FlowGraphOptimizer::TryReplaceWithStoreIndexed(InstanceCallInstr* call) { |
| const intptr_t class_id = ReceiverClassId(call); |
| ICData& value_check = ICData::ZoneHandle(); |
| switch (class_id) { |
| case kArrayCid: |
| case kGrowableObjectArrayCid: |
| if (ArgIsAlwaysSmi(*call->ic_data(), 2)) { |
| value_check = call->ic_data()->AsUnaryClassChecksForArgNr(2); |
| } |
| break; |
| case kTypedDataInt8ArrayCid: |
| case kTypedDataUint8ArrayCid: |
| case kTypedDataUint8ClampedArrayCid: |
| case kExternalTypedDataUint8ArrayCid: |
| case kExternalTypedDataUint8ClampedArrayCid: |
| case kTypedDataInt16ArrayCid: |
| case kTypedDataUint16ArrayCid: |
| // Check that value is always smi. |
| value_check = call->ic_data()->AsUnaryClassChecksForArgNr(2); |
| if ((value_check.NumberOfChecks() != 1) || |
| (value_check.GetReceiverClassIdAt(0) != kSmiCid)) { |
| return false; |
| } |
| break; |
| case kTypedDataInt32ArrayCid: |
| case kTypedDataUint32ArrayCid: { |
| if (!CanUnboxInt32()) return false; |
| // Check that value is always smi or mint, if the platform has unboxed |
| // mints (ia32 with at least SSE 4.1). |
| value_check = call->ic_data()->AsUnaryClassChecksForArgNr(2); |
| for (intptr_t i = 0; i < value_check.NumberOfChecks(); i++) { |
| intptr_t cid = value_check.GetReceiverClassIdAt(i); |
| if (FlowGraphCompiler::SupportsUnboxedMints()) { |
| if ((cid != kSmiCid) && (cid != kMintCid)) { |
| return false; |
| } |
| } else if (cid != kSmiCid) { |
| return false; |
| } |
| } |
| break; |
| } |
| case kTypedDataFloat32ArrayCid: |
| case kTypedDataFloat64ArrayCid: { |
| // Check that value is always double. |
| value_check = call->ic_data()->AsUnaryClassChecksForArgNr(2); |
| if ((value_check.NumberOfChecks() != 1) || |
| (value_check.GetReceiverClassIdAt(0) != kDoubleCid)) { |
| return false; |
| } |
| break; |
| } |
| case kTypedDataFloat32x4ArrayCid: { |
| // Check that value is always a Float32x4. |
| value_check = call->ic_data()->AsUnaryClassChecksForArgNr(2); |
| if ((value_check.NumberOfChecks() != 1) || |
| (value_check.GetReceiverClassIdAt(0) != kFloat32x4Cid)) { |
| return false; |
| } |
| } |
| break; |
| default: |
| // TODO(fschneider): Add support for other array types. |
| return false; |
| } |
| |
| BuildStoreIndexed(call, value_check, class_id); |
| return true; |
| } |
| |
| |
| void FlowGraphOptimizer::BuildStoreIndexed(InstanceCallInstr* call, |
| const ICData& value_check, |
| intptr_t class_id) { |
| Definition* array = call->ArgumentAt(0); |
| Definition* index = call->ArgumentAt(1); |
| Definition* stored_value = call->ArgumentAt(2); |
| if (FLAG_enable_type_checks) { |
| // Only type check for the value. A type check for the index is not |
| // needed here because we insert a deoptimizing smi-check for the case |
| // the index is not a smi. |
| const Function& target = |
| Function::ZoneHandle(call->ic_data()->GetTargetAt(0)); |
| const AbstractType& value_type = |
| AbstractType::ZoneHandle(target.ParameterTypeAt(2)); |
| Definition* instantiator = NULL; |
| Definition* type_args = NULL; |
| switch (class_id) { |
| case kArrayCid: |
| case kGrowableObjectArrayCid: { |
| const Class& instantiator_class = Class::Handle(target.Owner()); |
| intptr_t type_arguments_field_offset = |
| instantiator_class.type_arguments_field_offset(); |
| LoadFieldInstr* load_type_args = |
| new LoadFieldInstr(new Value(array), |
| type_arguments_field_offset, |
| Type::ZoneHandle()); // No type. |
| InsertBefore(call, load_type_args, NULL, Definition::kValue); |
| instantiator = array; |
| type_args = load_type_args; |
| break; |
| } |
| case kTypedDataInt8ArrayCid: |
| case kTypedDataUint8ArrayCid: |
| case kTypedDataUint8ClampedArrayCid: |
| case kExternalTypedDataUint8ArrayCid: |
| case kExternalTypedDataUint8ClampedArrayCid: |
| case kTypedDataInt16ArrayCid: |
| case kTypedDataUint16ArrayCid: |
| case kTypedDataInt32ArrayCid: |
| case kTypedDataUint32ArrayCid: |
| ASSERT(value_type.IsIntType()); |
| // Fall through. |
| case kTypedDataFloat32ArrayCid: |
| case kTypedDataFloat64ArrayCid: { |
| type_args = instantiator = flow_graph_->constant_null(); |
| ASSERT((class_id != kTypedDataFloat32ArrayCid && |
| class_id != kTypedDataFloat64ArrayCid) || |
| value_type.IsDoubleType()); |
| ASSERT(value_type.IsInstantiated()); |
| break; |
| } |
| case kTypedDataFloat32x4ArrayCid: { |
| type_args = instantiator = flow_graph_->constant_null(); |
| ASSERT((class_id != kTypedDataFloat32x4ArrayCid) || |
| value_type.IsFloat32x4Type()); |
| ASSERT(value_type.IsInstantiated()); |
| break; |
| } |
| default: |
| // TODO(fschneider): Add support for other array types. |
| UNREACHABLE(); |
| } |
| AssertAssignableInstr* assert_value = |
| new AssertAssignableInstr(call->token_pos(), |
| new Value(stored_value), |
| new Value(instantiator), |
| new Value(type_args), |
| value_type, |
| Symbols::Value()); |
| // Newly inserted instructions that can deoptimize or throw an exception |
| // must have a deoptimization id that is valid for lookup in the unoptimized |
| // code. |
| assert_value->deopt_id_ = call->deopt_id(); |
| InsertBefore(call, assert_value, call->env(), Definition::kValue); |
| } |
| |
| intptr_t array_cid = PrepareIndexedOp(call, class_id, &array, &index); |
| // Check if store barrier is needed. Byte arrays don't need a store barrier. |
| StoreBarrierType needs_store_barrier = |
| (RawObject::IsTypedDataClassId(array_cid) || |
| RawObject::IsTypedDataViewClassId(array_cid) || |
| RawObject::IsExternalTypedDataClassId(array_cid)) ? kNoStoreBarrier |
| : kEmitStoreBarrier; |
| if (!value_check.IsNull()) { |
| // No store barrier needed because checked value is a smi, an unboxed mint, |
| // an unboxed double, an unboxed Float32x4, or unboxed Uint32x4. |
| needs_store_barrier = kNoStoreBarrier; |
| AddCheckClass(stored_value, value_check, call->deopt_id(), call->env(), |
| call); |
| } |
| |
| intptr_t index_scale = FlowGraphCompiler::ElementSizeFor(array_cid); |
| Definition* array_op = new StoreIndexedInstr(new Value(array), |
| new Value(index), |
| new Value(stored_value), |
| needs_store_barrier, |
| index_scale, |
| array_cid, |
| call->deopt_id()); |
| ReplaceCall(call, array_op); |
| } |
| |
| |
| |
| bool FlowGraphOptimizer::TryReplaceWithLoadIndexed(InstanceCallInstr* call) { |
| const intptr_t class_id = ReceiverClassId(call); |
| // Set deopt_id to a valid id if the LoadIndexedInstr can cause deopt. |
| intptr_t deopt_id = Isolate::kNoDeoptId; |
| switch (class_id) { |
| case kArrayCid: |
| case kImmutableArrayCid: |
| case kGrowableObjectArrayCid: |
| case kTypedDataFloat32ArrayCid: |
| case kTypedDataFloat64ArrayCid: |
| case kTypedDataFloat32x4ArrayCid: |
| case kTypedDataInt8ArrayCid: |
| case kTypedDataUint8ArrayCid: |
| case kTypedDataUint8ClampedArrayCid: |
| case kExternalTypedDataUint8ArrayCid: |
| case kExternalTypedDataUint8ClampedArrayCid: |
| case kTypedDataInt16ArrayCid: |
| case kTypedDataUint16ArrayCid: |
| break; |
| case kTypedDataInt32ArrayCid: |
| case kTypedDataUint32ArrayCid: { |
| if (!CanUnboxInt32()) return false; |
| |
| // Set deopt_id if we can optimistically assume that the result is Smi. |
| // Assume mixed Mint/Smi if this instruction caused deoptimization once. |
| ASSERT(call->HasICData()); |
| const ICData& ic_data = *call->ic_data(); |
| deopt_id = (ic_data.deopt_reason() == kDeoptUnknown) ? |
| call->deopt_id() : Isolate::kNoDeoptId; |
| } |
| break; |
| default: |
| return false; |
| } |
| Definition* array = call->ArgumentAt(0); |
| Definition* index = call->ArgumentAt(1); |
| intptr_t array_cid = PrepareIndexedOp(call, class_id, &array, &index); |
| intptr_t index_scale = FlowGraphCompiler::ElementSizeFor(array_cid); |
| Definition* array_op = |
| new LoadIndexedInstr(new Value(array), |
| new Value(index), |
| index_scale, |
| array_cid, |
| deopt_id); |
| ReplaceCall(call, array_op); |
| return true; |
| } |
| |
| |
| bool FlowGraphOptimizer::TryReplaceWithBinaryOp(InstanceCallInstr* call, |
| Token::Kind op_kind) { |
| intptr_t operands_type = kIllegalCid; |
| ASSERT(call->HasICData()); |
| const ICData& ic_data = *call->ic_data(); |
| switch (op_kind) { |
| case Token::kADD: |
| case Token::kSUB: |
| if (HasOnlyTwoSmis(ic_data)) { |
| // Don't generate smi code if the IC data is marked because |
| // of an overflow. |
| operands_type = (ic_data.deopt_reason() == kDeoptBinarySmiOp) |
| ? kMintCid |
| : kSmiCid; |
| } else if (HasTwoMintOrSmi(ic_data) && |
| FlowGraphCompiler::SupportsUnboxedMints()) { |
| // Don't generate mint code if the IC data is marked because of an |
| // overflow. |
| if (ic_data.deopt_reason() == kDeoptBinaryMintOp) return false; |
| operands_type = kMintCid; |
| } else if (ShouldSpecializeForDouble(ic_data)) { |
| operands_type = kDoubleCid; |
| } else if (HasOnlyTwoFloat32x4s(ic_data)) { |
| operands_type = kFloat32x4Cid; |
| } else { |
| return false; |
| } |
| break; |
| case Token::kMUL: |
| if (HasOnlyTwoSmis(ic_data)) { |
| // Don't generate smi code if the IC data is marked because of an |
| // overflow. |
| // TODO(fschneider): Add unboxed mint multiplication. |
| if (ic_data.deopt_reason() == kDeoptBinarySmiOp) return false; |
| operands_type = kSmiCid; |
| } else if (ShouldSpecializeForDouble(ic_data)) { |
| operands_type = kDoubleCid; |
| } else if (HasOnlyTwoFloat32x4s(ic_data)) { |
| operands_type = kFloat32x4Cid; |
| } else { |
| return false; |
| } |
| break; |
| case Token::kDIV: |
| if (ShouldSpecializeForDouble(ic_data)) { |
| operands_type = kDoubleCid; |
| } else if (HasOnlyTwoFloat32x4s(ic_data)) { |
| operands_type = kFloat32x4Cid; |
| } else { |
| return false; |
| } |
| break; |
| case Token::kMOD: |
| if (HasOnlyTwoSmis(ic_data)) { |
| operands_type = kSmiCid; |
| } else { |
| return false; |
| } |
| break; |
| case Token::kBIT_AND: |
| case Token::kBIT_OR: |
| case Token::kBIT_XOR: |
| if (HasOnlyTwoSmis(ic_data)) { |
| operands_type = kSmiCid; |
| } else if (HasTwoMintOrSmi(ic_data)) { |
| operands_type = kMintCid; |
| } else { |
| return false; |
| } |
| break; |
| case Token::kSHR: |
| case Token::kSHL: |
| if (HasOnlyTwoSmis(ic_data)) { |
| // Left shift may overflow from smi into mint or big ints. |
| // Don't generate smi code if the IC data is marked because |
| // of an overflow. |
| if (ic_data.deopt_reason() == kDeoptShiftMintOp) return false; |
| operands_type = (ic_data.deopt_reason() == kDeoptBinarySmiOp) |
| ? kMintCid |
| : kSmiCid; |
| } else if (HasTwoMintOrSmi(ic_data) && |
| HasOnlyOneSmi(ICData::Handle( |
| ic_data.AsUnaryClassChecksForArgNr(1)))) { |
| // Don't generate mint code if the IC data is marked because of an |
| // overflow. |
| if (ic_data.deopt_reason() == kDeoptShiftMintOp) return false; |
| // Check for smi/mint << smi or smi/mint >> smi. |
| operands_type = kMintCid; |
| } else { |
| return false; |
| } |
| break; |
| case Token::kTRUNCDIV: |
| if (HasOnlyTwoSmis(ic_data)) { |
| if (ic_data.deopt_reason() == kDeoptBinarySmiOp) return false; |
| operands_type = kSmiCid; |
| } else { |
| return false; |
| } |
| break; |
| default: |
| UNREACHABLE(); |
| } |
| |
| ASSERT(call->ArgumentCount() == 2); |
| Definition* left = call->ArgumentAt(0); |
| Definition* right = call->ArgumentAt(1); |
| if (operands_type == kDoubleCid) { |
| // Check that either left or right are not a smi. Result of a |
| // binary operation with two smis is a smi not a double. |
| InsertBefore(call, |
| new CheckEitherNonSmiInstr(new Value(left), |
| new Value(right), |
| call), |
| call->env(), |
| Definition::kEffect); |
| |
| BinaryDoubleOpInstr* double_bin_op = |
| new BinaryDoubleOpInstr(op_kind, new Value(left), new Value(right), |
| call); |
| ReplaceCall(call, double_bin_op); |
| } else if (operands_type == kMintCid) { |
| if (!FlowGraphCompiler::SupportsUnboxedMints()) return false; |
| if ((op_kind == Token::kSHR) || (op_kind == Token::kSHL)) { |
| ShiftMintOpInstr* shift_op = |
| new ShiftMintOpInstr(op_kind, new Value(left), new Value(right), |
| call); |
| ReplaceCall(call, shift_op); |
| } else { |
| BinaryMintOpInstr* bin_op = |
| new BinaryMintOpInstr(op_kind, new Value(left), new Value(right), |
| call); |
| ReplaceCall(call, bin_op); |
| } |
| } else if (operands_type == kFloat32x4Cid) { |
| // Type check left. |
| AddCheckClass(left, |
| ICData::ZoneHandle( |
| call->ic_data()->AsUnaryClassChecksForArgNr(0)), |
| call->deopt_id(), |
| call->env(), |
| call); |
| // Type check right. |
| AddCheckClass(right, |
| ICData::ZoneHandle( |
| call->ic_data()->AsUnaryClassChecksForArgNr(1)), |
| call->deopt_id(), |
| call->env(), |
| call); |
| // Replace call. |
| BinaryFloat32x4OpInstr* float32x4_bin_op = |
| new BinaryFloat32x4OpInstr(op_kind, new Value(left), new Value(right), |
| call); |
| ReplaceCall(call, float32x4_bin_op); |
| } else if (op_kind == Token::kMOD) { |
| // TODO(vegorov): implement fast path code for modulo. |
| ASSERT(operands_type == kSmiCid); |
| if (!right->IsConstant()) return false; |
| const Object& obj = right->AsConstant()->value(); |
| if (!obj.IsSmi()) return false; |
| const intptr_t value = Smi::Cast(obj).Value(); |
| if ((value <= 0) || !Utils::IsPowerOfTwo(value)) return false; |
| |
| // Insert smi check and attach a copy of the original environment |
| // because the smi operation can still deoptimize. |
| InsertBefore(call, |
| new CheckSmiInstr(new Value(left), call->deopt_id()), |
| call->env(), |
| Definition::kEffect); |
| ConstantInstr* constant = |
| new ConstantInstr(Smi::Handle(Smi::New(value - 1))); |
| InsertBefore(call, constant, NULL, Definition::kValue); |
| BinarySmiOpInstr* bin_op = |
| new BinarySmiOpInstr(Token::kBIT_AND, call, |
| new Value(left), |
| new Value(constant)); |
| ReplaceCall(call, bin_op); |
| } else { |
| ASSERT(operands_type == kSmiCid); |
| // Insert two smi checks and attach a copy of the original |
| // environment because the smi operation can still deoptimize. |
| AddCheckSmi(left, call->deopt_id(), call->env(), call); |
| AddCheckSmi(right, call->deopt_id(), call->env(), call); |
| if (left->IsConstant() && |
| ((op_kind == Token::kADD) || (op_kind == Token::kMUL))) { |
| // Constant should be on the right side. |
| Definition* temp = left; |
| left = right; |
| right = temp; |
| } |
| BinarySmiOpInstr* bin_op = |
| new BinarySmiOpInstr(op_kind, call, new Value(left), new Value(right)); |
| ReplaceCall(call, bin_op); |
| } |
| return true; |
| } |
| |
| |
| bool FlowGraphOptimizer::TryReplaceWithUnaryOp(InstanceCallInstr* call, |
| Token::Kind op_kind) { |
| ASSERT(call->ArgumentCount() == 1); |
| Definition* input = call->ArgumentAt(0); |
| Definition* unary_op = NULL; |
| if (HasOnlyOneSmi(*call->ic_data())) { |
| InsertBefore(call, |
| new CheckSmiInstr(new Value(input), call->deopt_id()), |
| call->env(), |
| Definition::kEffect); |
| unary_op = new UnarySmiOpInstr(op_kind, call, new Value(input)); |
| } else if ((op_kind == Token::kBIT_NOT) && |
| HasOnlySmiOrMint(*call->ic_data()) && |
| FlowGraphCompiler::SupportsUnboxedMints()) { |
| unary_op = new UnaryMintOpInstr(op_kind, new Value(input), call); |
| } else if (HasOnlyOneDouble(*call->ic_data()) && |
| (op_kind == Token::kNEGATE)) { |
| AddReceiverCheck(call); |
| ConstantInstr* minus_one = |
| new ConstantInstr(Double::ZoneHandle(Double::NewCanonical(-1))); |
| InsertBefore(call, minus_one, NULL, Definition::kValue); |
| unary_op = new BinaryDoubleOpInstr(Token::kMUL, |
| new Value(input), |
| new Value(minus_one), |
| call); |
| } |
| if (unary_op == NULL) return false; |
| |
| ReplaceCall(call, unary_op); |
| return true; |
| } |
| |
| |
| // Using field class |
| static RawField* GetField(intptr_t class_id, const String& field_name) { |
| Class& cls = Class::Handle(Isolate::Current()->class_table()->At(class_id)); |
| Field& field = Field::Handle(); |
| while (!cls.IsNull()) { |
| field = cls.LookupInstanceField(field_name); |
| if (!field.IsNull()) { |
| return field.raw(); |
| } |
| cls = cls.SuperClass(); |
| } |
| return Field::null(); |
| } |
| |
| |
| // Use CHA to determine if the call needs a class check: if the callee's |
| // receiver is the same as the caller's receiver and there are no overriden |
| // callee functions, then no class check is needed. |
| bool FlowGraphOptimizer::InstanceCallNeedsClassCheck( |
| InstanceCallInstr* call) const { |
| if (!FLAG_use_cha) return true; |
| Definition* callee_receiver = call->ArgumentAt(0); |
| ASSERT(callee_receiver != NULL); |
| const Function& function = flow_graph_->parsed_function().function(); |
| if (function.IsDynamicFunction() && |
| callee_receiver->IsParameter() && |
| (callee_receiver->AsParameter()->index() == 0)) { |
| return CHA::HasOverride(Class::Handle(function.Owner()), |
| call->function_name()); |
| } |
| return true; |
| } |
| |
| |
| bool FlowGraphOptimizer::MethodExtractorNeedsClassCheck( |
| InstanceCallInstr* call) const { |
| if (!FLAG_use_cha) return true; |
| Definition* callee_receiver = call->ArgumentAt(0); |
| ASSERT(callee_receiver != NULL); |
| const Function& function = flow_graph_->parsed_function().function(); |
| if (function.IsDynamicFunction() && |
| callee_receiver->IsParameter() && |
| (callee_receiver->AsParameter()->index() == 0)) { |
| const String& field_name = |
| String::Handle(Field::NameFromGetter(call->function_name())); |
| return CHA::HasOverride(Class::Handle(function.Owner()), field_name); |
| } |
| return true; |
| } |
| |
| |
| void FlowGraphOptimizer::AddToGuardedFields(Field* field) { |
| if ((field->guarded_cid() == kDynamicCid) || |
| (field->guarded_cid() == kIllegalCid)) { |
| return; |
| } |
| for (intptr_t j = 0; j < guarded_fields_->length(); j++) { |
| if ((*guarded_fields_)[j]->raw() == field->raw()) { |
| return; |
| } |
| } |
| guarded_fields_->Add(field); |
| } |
| |
| |
| void FlowGraphOptimizer::InlineImplicitInstanceGetter(InstanceCallInstr* call) { |
| ASSERT(call->HasICData()); |
| const ICData& ic_data = *call->ic_data(); |
| Function& target = Function::Handle(); |
| GrowableArray<intptr_t> class_ids; |
| ic_data.GetCheckAt(0, &class_ids, &target); |
| ASSERT(class_ids.length() == 1); |
| // Inline implicit instance getter. |
| const String& field_name = |
| String::Handle(Field::NameFromGetter(call->function_name())); |
| const Field& field = Field::Handle(GetField(class_ids[0], field_name)); |
| ASSERT(!field.IsNull()); |
| |
| if (InstanceCallNeedsClassCheck(call)) { |
| AddReceiverCheck(call); |
| } |
| LoadFieldInstr* load = new LoadFieldInstr( |
| new Value(call->ArgumentAt(0)), |
| field.Offset(), |
| AbstractType::ZoneHandle(field.type()), |
| field.is_final()); |
| if (field.guarded_cid() != kIllegalCid) { |
| if (!field.is_nullable() || (field.guarded_cid() == kNullCid)) { |
| load->set_result_cid(field.guarded_cid()); |
| } |
| Field* the_field = &Field::ZoneHandle(field.raw()); |
| load->set_field(the_field); |
| AddToGuardedFields(the_field); |
| } |
| load->set_field_name(String::Handle(field.name()).ToCString()); |
| |
| // Discard the environment from the original instruction because the load |
| // can't deoptimize. |
| call->RemoveEnvironment(); |
| ReplaceCall(call, load); |
| |
| if (load->result_cid() != kDynamicCid) { |
| // Reset value types if guarded_cid was used. |
| for (Value::Iterator it(load->input_use_list()); |
| !it.Done(); |
| it.Advance()) { |
| it.Current()->SetReachingType(NULL); |
| } |
| } |
| } |
| |
| |
| void FlowGraphOptimizer::InlineArrayLengthGetter(InstanceCallInstr* call, |
| intptr_t length_offset, |
| bool is_immutable, |
| MethodRecognizer::Kind kind) { |
| AddReceiverCheck(call); |
| |
| LoadFieldInstr* load = new LoadFieldInstr( |
| new Value(call->ArgumentAt(0)), |
| length_offset, |
| Type::ZoneHandle(Type::SmiType()), |
| is_immutable); |
| load->set_result_cid(kSmiCid); |
| load->set_recognized_kind(kind); |
| ReplaceCall(call, load); |
| } |
| |
| |
| void FlowGraphOptimizer::InlineGrowableArrayCapacityGetter( |
| InstanceCallInstr* call) { |
| AddReceiverCheck(call); |
| |
| // TODO(srdjan): type of load should be GrowableObjectArrayType. |
| LoadFieldInstr* data_load = new LoadFieldInstr( |
| new Value(call->ArgumentAt(0)), |
| Array::data_offset(), |
| Type::ZoneHandle(Type::DynamicType())); |
| data_load->set_result_cid(kArrayCid); |
| InsertBefore(call, data_load, NULL, Definition::kValue); |
| |
| LoadFieldInstr* length_load = new LoadFieldInstr( |
| new Value(data_load), |
| Array::length_offset(), |
| Type::ZoneHandle(Type::SmiType())); |
| length_load->set_result_cid(kSmiCid); |
| length_load->set_recognized_kind(MethodRecognizer::kObjectArrayLength); |
| |
| ReplaceCall(call, length_load); |
| } |
| |
| |
| static LoadFieldInstr* BuildLoadStringLength(Definition* str) { |
| // Treat length loads as mutable (i.e. affected by side effects) to avoid |
| // hoisting them since we can't hoist the preceding class-check. This |
| // is because of externalization of strings that affects their class-id. |
| const bool is_immutable = false; |
| LoadFieldInstr* load = new LoadFieldInstr( |
| new Value(str), |
| String::length_offset(), |
| Type::ZoneHandle(Type::SmiType()), |
| is_immutable); |
| load->set_result_cid(kSmiCid); |
| load->set_recognized_kind(MethodRecognizer::kStringBaseLength); |
| return load; |
| } |
| |
| |
| void FlowGraphOptimizer::InlineStringLengthGetter(InstanceCallInstr* call) { |
| AddReceiverCheck(call); |
| LoadFieldInstr* load = BuildLoadStringLength(call->ArgumentAt(0)); |
| ReplaceCall(call, load); |
| } |
| |
| |
| void FlowGraphOptimizer::InlineStringIsEmptyGetter(InstanceCallInstr* call) { |
| AddReceiverCheck(call); |
| |
| LoadFieldInstr* load = BuildLoadStringLength(call->ArgumentAt(0)); |
| InsertBefore(call, load, NULL, Definition::kValue); |
| |
| ConstantInstr* zero = new ConstantInstr(Smi::Handle(Smi::New(0))); |
| InsertBefore(call, zero, NULL, Definition::kValue); |
| |
| StrictCompareInstr* compare = |
| new StrictCompareInstr(Token::kEQ_STRICT, |
| new Value(load), |
| new Value(zero)); |
| ReplaceCall(call, compare); |
| } |
| |
| |
| static intptr_t OffsetForLengthGetter(MethodRecognizer::Kind kind) { |
| switch (kind) { |
| case MethodRecognizer::kObjectArrayLength: |
| case MethodRecognizer::kImmutableArrayLength: |
| return Array::length_offset(); |
| case MethodRecognizer::kTypedDataLength: |
| // .length is defined in _TypedList which is the base class for internal |
| // and external typed data. |
| ASSERT(TypedData::length_offset() == ExternalTypedData::length_offset()); |
| return TypedData::length_offset(); |
| case MethodRecognizer::kGrowableArrayLength: |
| return GrowableObjectArray::length_offset(); |
| default: |
| UNREACHABLE(); |
| return 0; |
| } |
| } |
| |
| |
| bool FlowGraphOptimizer::InlineFloat32x4Getter(InstanceCallInstr* call, |
| MethodRecognizer::Kind getter) { |
| AddCheckClass(call->ArgumentAt(0), |
| ICData::ZoneHandle( |
| call->ic_data()->AsUnaryClassChecksForArgNr(0)), |
| call->deopt_id(), |
| call->env(), |
| call); |
| Float32x4ShuffleInstr* instr = new Float32x4ShuffleInstr( |
| getter, |
| new Value(call->ArgumentAt(0)), |
| call); |
| ReplaceCall(call, instr); |
| return true; |
| } |
| |
| |
| // Only unique implicit instance getters can be currently handled. |
| bool FlowGraphOptimizer::TryInlineInstanceGetter(InstanceCallInstr* call) { |
| ASSERT(call->HasICData()); |
| const ICData& ic_data = *call->ic_data(); |
| if (ic_data.NumberOfChecks() == 0) { |
| // No type feedback collected. |
| return false; |
| } |
| Function& target = Function::Handle(ic_data.GetTargetAt(0)); |
| if (target.kind() == RawFunction::kImplicitGetter) { |
| if (!ic_data.HasOneTarget()) { |
| // TODO(srdjan): Implement for mutiple targets. |
| return false; |
| } |
| InlineImplicitInstanceGetter(call); |
| return true; |
| } else if (target.kind() == RawFunction::kMethodExtractor) { |
| return false; |
| } |
| |
| // Not an implicit getter. |
| MethodRecognizer::Kind recognized_kind = |
| MethodRecognizer::RecognizeKind(target); |
| |
| // VM objects length getter. |
| switch (recognized_kind) { |
| case MethodRecognizer::kObjectArrayLength: |
| case MethodRecognizer::kImmutableArrayLength: |
| case MethodRecognizer::kTypedDataLength: |
| case MethodRecognizer::kGrowableArrayLength: { |
| if (!ic_data.HasOneTarget()) { |
| // TODO(srdjan): Implement for mutiple targets. |
| return false; |
| } |
| const bool is_immutable = |
| (recognized_kind == MethodRecognizer::kObjectArrayLength) || |
| (recognized_kind == MethodRecognizer::kImmutableArrayLength) || |
| (recognized_kind == MethodRecognizer::kTypedDataLength); |
| InlineArrayLengthGetter(call, |
| OffsetForLengthGetter(recognized_kind), |
| is_immutable, |
| recognized_kind); |
| return true; |
| } |
| case MethodRecognizer::kGrowableArrayCapacity: |
| InlineGrowableArrayCapacityGetter(call); |
| return true; |
| case MethodRecognizer::kStringBaseLength: |
| if (!ic_data.HasOneTarget()) { |
| // Target is not only StringBase_get_length. |
| return false; |
| } |
| InlineStringLengthGetter(call); |
| return true; |
| case MethodRecognizer::kStringBaseIsEmpty: |
| if (!ic_data.HasOneTarget()) { |
| // Target is not only StringBase_get_isEmpty. |
| return false; |
| } |
| InlineStringIsEmptyGetter(call); |
| return true; |
| case MethodRecognizer::kFloat32x4ShuffleXXXX: |
| case MethodRecognizer::kFloat32x4ShuffleYYYY: |
| case MethodRecognizer::kFloat32x4ShuffleZZZZ: |
| case MethodRecognizer::kFloat32x4ShuffleWWWW: |
| case MethodRecognizer::kFloat32x4ShuffleX: |
| case MethodRecognizer::kFloat32x4ShuffleY: |
| case MethodRecognizer::kFloat32x4ShuffleZ: |
| case MethodRecognizer::kFloat32x4ShuffleW: |
| if (!ic_data.HasReceiverClassId(kFloat32x4Cid) || |
| !ic_data.HasOneTarget()) { |
| return false; |
| } |
| return InlineFloat32x4Getter(call, recognized_kind); |
| default: |
| ASSERT(recognized_kind == MethodRecognizer::kUnknown); |
| } |
| return false; |
| } |
| |
| |
| LoadIndexedInstr* FlowGraphOptimizer::BuildStringCodeUnitAt( |
| InstanceCallInstr* call, |
| intptr_t cid) { |
| Definition* str = call->ArgumentAt(0); |
| Definition* index = call->ArgumentAt(1); |
| AddReceiverCheck(call); |
| InsertBefore(call, |
| new CheckSmiInstr(new Value(index), call->deopt_id()), |
| call->env(), |
| Definition::kEffect); |
| // If both index and string are constants, then do a compile-time check. |
| // TODO(srdjan): Remove once constant propagation handles bounds checks. |
| bool skip_check = false; |
| if (str->IsConstant() && index->IsConstant()) { |
| const String& constant_string = |
| String::Cast(str->AsConstant()->value()); |
| const Object& constant_index = index->AsConstant()->value(); |
| skip_check = constant_index.IsSmi() && |
| (Smi::Cast(constant_index).Value() < constant_string.Length()); |
| } |
| if (!skip_check) { |
| // Insert bounds check. |
| LoadFieldInstr* length = BuildLoadStringLength(str); |
| InsertBefore(call, length, NULL, Definition::kValue); |
| InsertBefore(call, |
| new CheckArrayBoundInstr(new Value(length), |
| new Value(index), |
| cid, |
| call), |
| call->env(), |
| Definition::kEffect); |
| } |
| return new LoadIndexedInstr(new Value(str), |
| new Value(index), |
| FlowGraphCompiler::ElementSizeFor(cid), |
| cid, |
| Isolate::kNoDeoptId); // Can't deoptimize. |
| } |
| |
| |
| void FlowGraphOptimizer::ReplaceWithMathCFunction( |
| InstanceCallInstr* call, |
| MethodRecognizer::Kind recognized_kind) { |
| AddReceiverCheck(call); |
| ZoneGrowableArray<Value*>* args = |
| new ZoneGrowableArray<Value*>(call->ArgumentCount()); |
| for (intptr_t i = 0; i < call->ArgumentCount(); i++) { |
| args->Add(new Value(call->ArgumentAt(i))); |
| } |
| InvokeMathCFunctionInstr* invoke = |
| new InvokeMathCFunctionInstr(args, call, recognized_kind); |
| ReplaceCall(call, invoke); |
| } |
| |
| |
| static bool IsSupportedByteArrayViewCid(intptr_t cid) { |
| switch (cid) { |
| case kTypedDataInt8ArrayCid: |
| case kTypedDataUint8ArrayCid: |
| case kExternalTypedDataUint8ArrayCid: |
| case kTypedDataUint8ClampedArrayCid: |
| case kExternalTypedDataUint8ClampedArrayCid: |
| case kTypedDataInt16ArrayCid: |
| case kTypedDataUint16ArrayCid: |
| case kTypedDataInt32ArrayCid: |
| case kTypedDataUint32ArrayCid: |
| case kTypedDataFloat32ArrayCid: |
| case kTypedDataFloat64ArrayCid: |
| case kTypedDataFloat32x4ArrayCid: |
| return true; |
| default: |
| return false; |
| } |
| } |
| |
| |
| // Inline only simple, frequently called core library methods. |
| bool FlowGraphOptimizer::TryInlineInstanceMethod(InstanceCallInstr* call) { |
| ASSERT(call->HasICData()); |
| const ICData& ic_data = *call->ic_data(); |
| if ((ic_data.NumberOfChecks() == 0) || !ic_data.HasOneTarget()) { |
| // No type feedback collected or multiple targets found. |
| return false; |
| } |
| |
| Function& target = Function::Handle(); |
| GrowableArray<intptr_t> class_ids; |
| ic_data.GetCheckAt(0, &class_ids, &target); |
| MethodRecognizer::Kind recognized_kind = |
| MethodRecognizer::RecognizeKind(target); |
| |
| if ((recognized_kind == MethodRecognizer::kStringBaseCodeUnitAt) && |
| (ic_data.NumberOfChecks() == 1) && |
| ((class_ids[0] == kOneByteStringCid) || |
| (class_ids[0] == kTwoByteStringCid))) { |
| LoadIndexedInstr* instr = BuildStringCodeUnitAt(call, class_ids[0]); |
| ReplaceCall(call, instr); |
| return true; |
| } |
| if ((recognized_kind == MethodRecognizer::kStringBaseCharAt) && |
| (ic_data.NumberOfChecks() == 1) && |
| (class_ids[0] == kOneByteStringCid)) { |
| // TODO(fschneider): Handle TwoByteString. |
| LoadIndexedInstr* load_char_code = |
| BuildStringCodeUnitAt(call, class_ids[0]); |
| InsertBefore(call, load_char_code, NULL, Definition::kValue); |
| StringFromCharCodeInstr* char_at = |
| new StringFromCharCodeInstr(new Value(load_char_code), |
| kOneByteStringCid); |
| ReplaceCall(call, char_at); |
| return true; |
| } |
| |
| if ((recognized_kind == MethodRecognizer::kIntegerToDouble) && |
| (ic_data.NumberOfChecks() == 1) && |
| (class_ids[0] == kSmiCid)) { |
| AddReceiverCheck(call); |
| ReplaceCall(call, new SmiToDoubleInstr(new Value(call->ArgumentAt(0)))); |
| return true; |
| } |
| |
| if (class_ids[0] == kDoubleCid) { |
| switch (recognized_kind) { |
| case MethodRecognizer::kDoubleToInteger: { |
| AddReceiverCheck(call); |
| ASSERT(call->HasICData()); |
| const ICData& ic_data = *call->ic_data(); |
| Definition* input = call->ArgumentAt(0); |
| Definition* d2i_instr = NULL; |
| if (ic_data.deopt_reason() == kDeoptDoubleToSmi) { |
| // Do not repeatedly deoptimize because result didn't fit into Smi. |
| d2i_instr = new DoubleToIntegerInstr(new Value(input), call); |
| } else { |
| // Optimistically assume result fits into Smi. |
| d2i_instr = new DoubleToSmiInstr(new Value(input), call); |
| } |
| ReplaceCall(call, d2i_instr); |
| return true; |
| } |
| case MethodRecognizer::kDoubleMod: |
| case MethodRecognizer::kDoublePow: |
| case MethodRecognizer::kDoubleRound: |
| ReplaceWithMathCFunction(call, recognized_kind); |
| return true; |
| case MethodRecognizer::kDoubleTruncate: |
| case MethodRecognizer::kDoubleFloor: |
| case MethodRecognizer::kDoubleCeil: |
| if (!CPUFeatures::double_truncate_round_supported()) { |
| ReplaceWithMathCFunction(call, recognized_kind); |
| } else { |
| AddReceiverCheck(call); |
| DoubleToDoubleInstr* d2d_instr = |
| new DoubleToDoubleInstr(new Value(call->ArgumentAt(0)), |
| call, |
| recognized_kind); |
| ReplaceCall(call, d2d_instr); |
| } |
| return true; |
| default: |
| // Unsupported method. |
| return false; |
| } |
| } |
| |
| if (IsSupportedByteArrayViewCid(class_ids[0]) && |
| (ic_data.NumberOfChecks() == 1)) { |
| // For elements that may not fit into a smi on all platforms, check if |
| // elements fit into a smi or the platform supports unboxed mints. |
| if ((recognized_kind == MethodRecognizer::kByteArrayBaseGetInt32) || |
| (recognized_kind == MethodRecognizer::kByteArrayBaseGetUint32) || |
| (recognized_kind == MethodRecognizer::kByteArrayBaseSetInt32) || |
| (recognized_kind == MethodRecognizer::kByteArrayBaseSetUint32)) { |
| if (!CanUnboxInt32()) return false; |
| } |
| |
| switch (recognized_kind) { |
| // ByteArray getters. |
| case MethodRecognizer::kByteArrayBaseGetInt8: |
| return BuildByteArrayViewLoad( |
| call, class_ids[0], kTypedDataInt8ArrayCid); |
| case MethodRecognizer::kByteArrayBaseGetUint8: |
| return BuildByteArrayViewLoad( |
| call, class_ids[0], kTypedDataUint8ArrayCid); |
| case MethodRecognizer::kByteArrayBaseGetInt16: |
| return BuildByteArrayViewLoad( |
| call, class_ids[0], kTypedDataInt16ArrayCid); |
| case MethodRecognizer::kByteArrayBaseGetUint16: |
| return BuildByteArrayViewLoad( |
| call, class_ids[0], kTypedDataUint16ArrayCid); |
| case MethodRecognizer::kByteArrayBaseGetInt32: |
| return BuildByteArrayViewLoad( |
| call, class_ids[0], kTypedDataInt32ArrayCid); |
| case MethodRecognizer::kByteArrayBaseGetUint32: |
| return BuildByteArrayViewLoad( |
| call, class_ids[0], kTypedDataUint32ArrayCid); |
| case MethodRecognizer::kByteArrayBaseGetFloat32: |
| return BuildByteArrayViewLoad( |
| call, class_ids[0], kTypedDataFloat32ArrayCid); |
| case MethodRecognizer::kByteArrayBaseGetFloat64: |
| return BuildByteArrayViewLoad( |
| call, class_ids[0], kTypedDataFloat64ArrayCid); |
| case MethodRecognizer::kByteArrayBaseGetFloat32x4: |
| return BuildByteArrayViewLoad( |
| call, class_ids[0], kTypedDataFloat32x4ArrayCid); |
| |
| // ByteArray setters. |
| case MethodRecognizer::kByteArrayBaseSetInt8: |
| return BuildByteArrayViewStore( |
| call, class_ids[0], kTypedDataInt8ArrayCid); |
| case MethodRecognizer::kByteArrayBaseSetUint8: |
| return BuildByteArrayViewStore( |
| call, class_ids[0], kTypedDataUint8ArrayCid); |
| case MethodRecognizer::kByteArrayBaseSetInt16: |
| return BuildByteArrayViewStore( |
| call, class_ids[0], kTypedDataInt16ArrayCid); |
| case MethodRecognizer::kByteArrayBaseSetUint16: |
| return BuildByteArrayViewStore( |
| call, class_ids[0], kTypedDataUint16ArrayCid); |
| case MethodRecognizer::kByteArrayBaseSetInt32: |
| return BuildByteArrayViewStore( |
| call, class_ids[0], kTypedDataInt32ArrayCid); |
| case MethodRecognizer::kByteArrayBaseSetUint32: |
| return BuildByteArrayViewStore( |
| call, class_ids[0], kTypedDataUint32ArrayCid); |
| case MethodRecognizer::kByteArrayBaseSetFloat32: |
| return BuildByteArrayViewStore( |
| call, class_ids[0], kTypedDataFloat32ArrayCid); |
| case MethodRecognizer::kByteArrayBaseSetFloat64: |
| return BuildByteArrayViewStore( |
| call, class_ids[0], kTypedDataFloat64ArrayCid); |
| case MethodRecognizer::kByteArrayBaseSetFloat32x4: |
| return BuildByteArrayViewStore( |
| call, class_ids[0], kTypedDataFloat32x4ArrayCid); |
| default: |
| // Unsupported method. |
| return false; |
| } |
| } |
| |
| if ((class_ids[0] == kFloat32x4Cid) && (ic_data.NumberOfChecks() == 1)) { |
| switch (recognized_kind) { |
| case MethodRecognizer::kFloat32x4Equal: |
| case MethodRecognizer::kFloat32x4GreaterThan: |
| case MethodRecognizer::kFloat32x4GreaterThanOrEqual: |
| case MethodRecognizer::kFloat32x4LessThan: |
| case MethodRecognizer::kFloat32x4LessThanOrEqual: |
| case MethodRecognizer::kFloat32x4NotEqual: { |
| Definition* left = call->ArgumentAt(0); |
| Definition* right = call->ArgumentAt(1); |
| // Type check left. |
| AddCheckClass(left, |
| ICData::ZoneHandle( |
| call->ic_data()->AsUnaryClassChecksForArgNr(0)), |
| call->deopt_id(), |
| call->env(), |
| call); |
| // Replace call. |
| Float32x4ComparisonInstr* cmp = |
| new Float32x4ComparisonInstr(recognized_kind, new Value(left), |
| new Value(right), call); |
| ReplaceCall(call, cmp); |
| return true; |
| } |
| case MethodRecognizer::kFloat32x4Min: |
| case MethodRecognizer::kFloat32x4Max: { |
| Definition* left = call->ArgumentAt(0); |
| Definition* right = call->ArgumentAt(1); |
| // Type check left. |
| AddCheckClass(left, |
| ICData::ZoneHandle( |
| call->ic_data()->AsUnaryClassChecksForArgNr(0)), |
| call->deopt_id(), |
| call->env(), |
| call); |
| Float32x4MinMaxInstr* minmax = |
| new Float32x4MinMaxInstr(recognized_kind, new Value(left), |
| new Value(right), call); |
| ReplaceCall(call, minmax); |
| return true; |
| } |
| case MethodRecognizer::kFloat32x4Scale: { |
| Definition* left = call->ArgumentAt(0); |
| Definition* right = call->ArgumentAt(1); |
| // Type check left. |
| AddCheckClass(left, |
| ICData::ZoneHandle( |
| call->ic_data()->AsUnaryClassChecksForArgNr(0)), |
| call->deopt_id(), |
| call->env(), |
| call); |
| // Left and right values are swapped when handed to the instruction, |
| // this is done so that the double value is loaded into the output |
| // register and can be destroyed. |
| Float32x4ScaleInstr* scale = |
| new Float32x4ScaleInstr(recognized_kind, new Value(right), |
| new Value(left), call); |
| ReplaceCall(call, scale); |
| return true; |
| } |
| case MethodRecognizer::kFloat32x4Sqrt: |
| case MethodRecognizer::kFloat32x4ReciprocalSqrt: |
| case MethodRecognizer::kFloat32x4Reciprocal: { |
| Definition* left = call->ArgumentAt(0); |
| AddCheckClass(left, |
| ICData::ZoneHandle( |
| call->ic_data()->AsUnaryClassChecksForArgNr(0)), |
| call->deopt_id(), |
| call->env(), |
| call); |
| Float32x4SqrtInstr* sqrt = |
| new Float32x4SqrtInstr(recognized_kind, new Value(left), call); |
| ReplaceCall(call, sqrt); |
| return true; |
| } |
| default: |
| return false; |
| } |
| } |
| return false; |
| } |
| |
| |
| bool FlowGraphOptimizer::BuildByteArrayViewLoad( |
| InstanceCallInstr* call, |
| intptr_t receiver_cid, |
| intptr_t view_cid) { |
| Definition* array = call->ArgumentAt(0); |
| PrepareByteArrayViewOp(call, receiver_cid, view_cid, &array); |
| |
| // Optimistically build a smi-checked load for Int32 and Uint32 |
| // loads on ia32 like we do for normal array loads, and only revert to |
| // mint case after deoptimizing here. |
| intptr_t deopt_id = Isolate::kNoDeoptId; |
| if ((view_cid == kTypedDataInt32ArrayCid || |
| view_cid == kTypedDataUint32ArrayCid) && |
| call->ic_data()->deopt_reason() == kDeoptUnknown) { |
| deopt_id = call->deopt_id(); |
| } |
| Definition* byte_index = call->ArgumentAt(1); |
| LoadIndexedInstr* array_op = new LoadIndexedInstr(new Value(array), |
| new Value(byte_index), |
| 1, // Index scale. |
| view_cid, |
| deopt_id); |
| ReplaceCall(call, array_op); |
| return true; |
| } |
| |
| |
| bool FlowGraphOptimizer::BuildByteArrayViewStore( |
| InstanceCallInstr* call, |
| intptr_t receiver_cid, |
| intptr_t view_cid) { |
| Definition* array = call->ArgumentAt(0); |
| PrepareByteArrayViewOp(call, receiver_cid, view_cid, &array); |
| ICData& value_check = ICData::ZoneHandle(); |
| switch (view_cid) { |
| case kTypedDataInt8ArrayCid: |
| case kTypedDataUint8ArrayCid: |
| case kTypedDataUint8ClampedArrayCid: |
| case kExternalTypedDataUint8ArrayCid: |
| case kExternalTypedDataUint8ClampedArrayCid: |
| case kTypedDataInt16ArrayCid: |
| case kTypedDataUint16ArrayCid: { |
| // Check that value is always smi. |
| value_check = ICData::New(Function::Handle(), |
| String::Handle(), |
| Isolate::kNoDeoptId, |
| 1); |
| value_check.AddReceiverCheck(kSmiCid, Function::Handle()); |
| break; |
| } |
| case kTypedDataInt32ArrayCid: |
| case kTypedDataUint32ArrayCid: |
| // We don't have ICData for the value stored, so we optimistically assume |
| // smis first. If we ever deoptimized here, we require to unbox the value |
| // before storing to handle the mint case, too. |
| if (call->ic_data()->deopt_reason() == kDeoptUnknown) { |
| value_check = ICData::New(Function::Handle(), |
| String::Handle(), |
| Isolate::kNoDeoptId, |
| 1); |
| value_check.AddReceiverCheck(kSmiCid, Function::Handle()); |
| } |
| break; |
| case kTypedDataFloat32ArrayCid: |
| case kTypedDataFloat64ArrayCid: { |
| // Check that value is always double. |
| value_check = ICData::New(Function::Handle(), |
| String::Handle(), |
| Isolate::kNoDeoptId, |
| 1); |
| value_check.AddReceiverCheck(kDoubleCid, Function::Handle()); |
| break; |
| } |
| case kTypedDataFloat32x4ArrayCid: { |
| // Check that value is always Float32x4. |
| value_check = ICData::New(Function::Handle(), |
| String::Handle(), |
| Isolate::kNoDeoptId, |
| 1); |
| value_check.AddReceiverCheck(kFloat32x4Cid, Function::Handle()); |
| break; |
| } |
| default: |
| // Array cids are already checked in the caller. |
| UNREACHABLE(); |
| } |
| |
| Definition* index = call->ArgumentAt(1); |
| Definition* stored_value = call->ArgumentAt(2); |
| if (!value_check.IsNull()) { |
| AddCheckClass(stored_value, value_check, call->deopt_id(), call->env(), |
| call); |
| } |
| StoreBarrierType needs_store_barrier = kNoStoreBarrier; |
| StoreIndexedInstr* array_op = new StoreIndexedInstr(new Value(array), |
| new Value(index), |
| new Value(stored_value), |
| needs_store_barrier, |
| 1, // Index scale |
| view_cid, |
| call->deopt_id()); |
| ReplaceCall(call, array_op); |
| return true; |
| } |
| |
| |
| void FlowGraphOptimizer::PrepareByteArrayViewOp( |
| InstanceCallInstr* call, |
| intptr_t receiver_cid, |
| intptr_t view_cid, |
| Definition** array) { |
| Definition* byte_index = call->ArgumentAt(1); |
| |
| AddReceiverCheck(call); |
| const bool is_immutable = true; |
| LoadFieldInstr* length = new LoadFieldInstr( |
| new Value(*array), |
| CheckArrayBoundInstr::LengthOffsetFor(receiver_cid), |
| Type::ZoneHandle(Type::SmiType()), |
| is_immutable); |
| length->set_result_cid(kSmiCid); |
| length->set_recognized_kind( |
| LoadFieldInstr::RecognizedKindFromArrayCid(receiver_cid)); |
| InsertBefore(call, length, NULL, Definition::kValue); |
| |
| // len_in_bytes = length * kBytesPerElement(receiver) |
| intptr_t element_size = FlowGraphCompiler::ElementSizeFor(receiver_cid); |
| ConstantInstr* bytes_per_element = |
| new ConstantInstr(Smi::Handle(Smi::New(element_size))); |
| InsertBefore(call, bytes_per_element, NULL, Definition::kValue); |
| BinarySmiOpInstr* len_in_bytes = |
| new BinarySmiOpInstr(Token::kMUL, |
| call, |
| new Value(length), |
| new Value(bytes_per_element)); |
| InsertBefore(call, len_in_bytes, call->env(), Definition::kValue); |
| |
| // Check byte_index < len_in_bytes. |
| InsertBefore(call, |
| new CheckArrayBoundInstr(new Value(len_in_bytes), |
| new Value(byte_index), |
| receiver_cid, |
| call), |
| call->env(), |
| Definition::kEffect); |
| |
| // Insert load of elements for external typed arrays. |
| if (RawObject::IsExternalTypedDataClassId(receiver_cid)) { |
| LoadUntaggedInstr* elements = |
| new LoadUntaggedInstr(new Value(*array), |
| ExternalTypedData::data_offset()); |
| InsertBefore(call, elements, NULL, Definition::kValue); |
| *array = elements; |
| } |
| } |
| |
| |
| // Returns a Boolean constant if all classes in ic_data yield the same type-test |
| // result and the type tests do not depend on type arguments. Otherwise return |
| // Bool::null(). |
| RawBool* FlowGraphOptimizer::InstanceOfAsBool(const ICData& ic_data, |
| const AbstractType& type) const { |
| ASSERT(ic_data.num_args_tested() == 1); // Unary checks only. |
| if (!type.IsInstantiated() || type.IsMalformed()) return Bool::null(); |
| const Class& type_class = Class::Handle(type.type_class()); |
| if (type_class.HasTypeArguments()) { |
| // Only raw types can be directly compared, thus disregarding type |
| // arguments. |
| const AbstractTypeArguments& type_arguments = |
| AbstractTypeArguments::Handle(type.arguments()); |
| const bool is_raw_type = type_arguments.IsNull() || |
| type_arguments.IsRaw(type_arguments.Length()); |
| if (!is_raw_type) { |
| // Unknown result. |
| return Bool::null(); |
| } |
| } |
| const ClassTable& class_table = *Isolate::Current()->class_table(); |
| Bool& prev = Bool::Handle(); |
| Class& cls = Class::Handle(); |
| for (int i = 0; i < ic_data.NumberOfChecks(); i++) { |
| cls = class_table.At(ic_data.GetReceiverClassIdAt(i)); |
| if (cls.HasTypeArguments()) return Bool::null(); |
| const bool is_subtype = cls.IsSubtypeOf(TypeArguments::Handle(), |
| type_class, |
| TypeArguments::Handle(), |
| NULL); |
| if (prev.IsNull()) { |
| prev = is_subtype ? Bool::True().raw() : Bool::False().raw(); |
| } else { |
| if (is_subtype != prev.value()) return Bool::null(); |
| } |
| } |
| return prev.raw(); |
| } |
| |
| |
| // TODO(srdjan): Use ICData to check if always true or false. |
| void FlowGraphOptimizer::ReplaceWithInstanceOf(InstanceCallInstr* call) { |
| ASSERT(Token::IsTypeTestOperator(call->token_kind())); |
| Definition* left = call->ArgumentAt(0); |
| Definition* instantiator = call->ArgumentAt(1); |
| Definition* type_args = call->ArgumentAt(2); |
| const AbstractType& type = |
| AbstractType::Cast(call->ArgumentAt(3)->AsConstant()->value()); |
| const bool negate = |
| Bool::Cast(call->ArgumentAt(4)->AsConstant()->value()).value(); |
| const ICData& unary_checks = |
| ICData::ZoneHandle(call->ic_data()->AsUnaryClassChecks()); |
| if (unary_checks.NumberOfChecks() <= FLAG_max_polymorphic_checks) { |
| Bool& as_bool = Bool::ZoneHandle(InstanceOfAsBool(unary_checks, type)); |
| if (!as_bool.IsNull()) { |
| AddReceiverCheck(call); |
| if (negate) { |
| as_bool = Bool::Get(!as_bool.value()); |
| } |
| ConstantInstr* bool_const = new ConstantInstr(as_bool); |
| ReplaceCall(call, bool_const); |
| return; |
| } |
| } |
| InstanceOfInstr* instance_of = |
| new InstanceOfInstr(call->token_pos(), |
| new Value(left), |
| new Value(instantiator), |
| new Value(type_args), |
| type, |
| negate, |
| call->deopt_id()); |
| ReplaceCall(call, instance_of); |
| } |
| |
| |
| void FlowGraphOptimizer::ReplaceWithTypeCast(InstanceCallInstr* call) { |
| ASSERT(Token::IsTypeCastOperator(call->token_kind())); |
| Definition* left = call->ArgumentAt(0); |
| Definition* instantiator = call->ArgumentAt(1); |
| Definition* type_args = call->ArgumentAt(2); |
| const AbstractType& type = |
| AbstractType::Cast(call->ArgumentAt(3)->AsConstant()->value()); |
| ASSERT(!type.IsMalformed()); |
| const ICData& unary_checks = |
| ICData::ZoneHandle(call->ic_data()->AsUnaryClassChecks()); |
| if (unary_checks.NumberOfChecks() <= FLAG_max_polymorphic_checks) { |
| Bool& as_bool = Bool::ZoneHandle(InstanceOfAsBool(unary_checks, type)); |
| if (as_bool.raw() == Bool::True().raw()) { |
| AddReceiverCheck(call); |
| // Remove the original push arguments. |
| for (intptr_t i = 0; i < call->ArgumentCount(); ++i) { |
| PushArgumentInstr* push = call->PushArgumentAt(i); |
| push->ReplaceUsesWith(push->value()->definition()); |
| push->RemoveFromGraph(); |
| } |
| // Remove call, replace it with 'left'. |
| call->ReplaceUsesWith(left); |
| call->RemoveFromGraph(); |
| return; |
| } |
| } |
| const String& dst_name = String::ZoneHandle( |
| Symbols::New(Exceptions::kCastErrorDstName)); |
| AssertAssignableInstr* assert_as = |
| new AssertAssignableInstr(call->token_pos(), |
| new Value(left), |
| new Value(instantiator), |
| new Value(type_args), |
| type, |
| dst_name); |
| // Newly inserted instructions that can deoptimize or throw an exception |
| // must have a deoptimization id that is valid for lookup in the unoptimized |
| // code. |
| assert_as->deopt_id_ = call->deopt_id(); |
| ReplaceCall(call, assert_as); |
| } |
| |
| |
| // Tries to optimize instance call by replacing it with a faster instruction |
| // (e.g, binary op, field load, ..). |
| void FlowGraphOptimizer::VisitInstanceCall(InstanceCallInstr* instr) { |
| if (!instr->HasICData() || (instr->ic_data()->NumberOfChecks() == 0)) { |
| return; |
| } |
| |
| const Token::Kind op_kind = instr->token_kind(); |
| // Type test is special as it always gets converted into inlined code. |
| if (Token::IsTypeTestOperator(op_kind)) { |
| ReplaceWithInstanceOf(instr); |
| return; |
| } |
| |
| if (Token::IsTypeCastOperator(op_kind)) { |
| ReplaceWithTypeCast(instr); |
| return; |
| } |
| |
| const ICData& unary_checks = |
| ICData::ZoneHandle(instr->ic_data()->AsUnaryClassChecks()); |
| |
| if ((unary_checks.NumberOfChecks() > FLAG_max_polymorphic_checks) && |
| InstanceCallNeedsClassCheck(instr)) { |
| // Too many checks, it will be megamorphic which needs unary checks. |
| instr->set_ic_data(&unary_checks); |
| return; |
| } |
| |
| if ((op_kind == Token::kASSIGN_INDEX) && TryReplaceWithStoreIndexed(instr)) { |
| return; |
| } |
| if ((op_kind == Token::kINDEX) && TryReplaceWithLoadIndexed(instr)) { |
| return; |
| } |
| if (Token::IsBinaryOperator(op_kind) && |
| TryReplaceWithBinaryOp(instr, op_kind)) { |
| return; |
| } |
| if (Token::IsPrefixOperator(op_kind) && |
| TryReplaceWithUnaryOp(instr, op_kind)) { |
| return; |
| } |
| if ((op_kind == Token::kGET) && TryInlineInstanceGetter(instr)) { |
| return; |
| } |
| if ((op_kind == Token::kSET) && |
| TryInlineInstanceSetter(instr, unary_checks)) { |
| return; |
| } |
| if (TryInlineInstanceMethod(instr)) { |
| return; |
| } |
| |
| const bool has_one_target = unary_checks.HasOneTarget(); |
| |
| if (has_one_target) { |
| const bool is_method_extraction = |
| Function::Handle(unary_checks.GetTargetAt(0)).IsMethodExtractor(); |
| |
| if ((is_method_extraction && !MethodExtractorNeedsClassCheck(instr)) || |
| (!is_method_extraction && !InstanceCallNeedsClassCheck(instr))) { |
| const bool call_with_checks = false; |
| PolymorphicInstanceCallInstr* call = |
| new PolymorphicInstanceCallInstr(instr, unary_checks, |
| call_with_checks); |
| instr->ReplaceWith(call, current_iterator()); |
| return; |
| } |
| } |
| |
| if (unary_checks.NumberOfChecks() <= FLAG_max_polymorphic_checks) { |
| bool call_with_checks; |
| if (has_one_target) { |
| // Type propagation has not run yet, we cannot eliminate the check. |
| AddReceiverCheck(instr); |
| // Call can still deoptimize, do not detach environment from instr. |
| call_with_checks = false; |
| } else { |
| call_with_checks = true; |
| } |
| PolymorphicInstanceCallInstr* call = |
| new PolymorphicInstanceCallInstr(instr, unary_checks, |
| call_with_checks); |
| instr->ReplaceWith(call, current_iterator()); |
| } |
| } |
| |
| |
| void FlowGraphOptimizer::VisitStaticCall(StaticCallInstr* call) { |
| MethodRecognizer::Kind recognized_kind = |
| MethodRecognizer::RecognizeKind(call->function()); |
| if (recognized_kind == MethodRecognizer::kMathSqrt) { |
| MathSqrtInstr* sqrt = |
| new MathSqrtInstr(new Value(call->ArgumentAt(0)), call); |
| ReplaceCall(call, sqrt); |
| } else if (recognized_kind == MethodRecognizer::kFloat32x4Zero) { |
| Float32x4ZeroInstr* zero = new Float32x4ZeroInstr(call); |
| ReplaceCall(call, zero); |
| } else if (recognized_kind == MethodRecognizer::kFloat32x4Splat) { |
| Float32x4SplatInstr* splat = |
| new Float32x4SplatInstr(new Value(call->ArgumentAt(1)), call); |
| ReplaceCall(call, splat); |
| } else if (recognized_kind == MethodRecognizer::kFloat32x4Constructor) { |
| Float32x4ConstructorInstr* con = |
| new Float32x4ConstructorInstr(new Value(call->ArgumentAt(1)), |
| new Value(call->ArgumentAt(2)), |
| new Value(call->ArgumentAt(3)), |
| new Value(call->ArgumentAt(4)), |
| call); |
| ReplaceCall(call, con); |
| } |
| } |
| |
| |
| bool FlowGraphOptimizer::TryInlineInstanceSetter(InstanceCallInstr* instr, |
| const ICData& unary_ic_data) { |
| ASSERT((unary_ic_data.NumberOfChecks() > 0) && |
| (unary_ic_data.num_args_tested() == 1)); |
| if (FLAG_enable_type_checks) { |
| // TODO(srdjan): Add assignable check node if --enable_type_checks. |
| return false; |
| } |
| |
| ASSERT(instr->HasICData()); |
| if (unary_ic_data.NumberOfChecks() == 0) { |
| // No type feedback collected. |
| return false; |
| } |
| if (!unary_ic_data.HasOneTarget()) { |
| // TODO(srdjan): Implement when not all targets are the same. |
| return false; |
| } |
| Function& target = Function::Handle(); |
| intptr_t class_id; |
| unary_ic_data.GetOneClassCheckAt(0, &class_id, &target); |
| if (target.kind() != RawFunction::kImplicitSetter) { |
| // Not an implicit setter. |
| // TODO(srdjan): Inline special setters. |
| return false; |
| } |
| // Inline implicit instance setter. |
| const String& field_name = |
| String::Handle(Field::NameFromSetter(instr->function_name())); |
| const Field& field = Field::Handle(GetField(class_id, field_name)); |
| ASSERT(!field.IsNull()); |
| |
| if (InstanceCallNeedsClassCheck(instr)) { |
| AddReceiverCheck(instr); |
| } |
| StoreBarrierType needs_store_barrier = kEmitStoreBarrier; |
| if (ArgIsAlwaysSmi(*instr->ic_data(), 1)) { |
| InsertBefore(instr, |
| new CheckSmiInstr(new Value(instr->ArgumentAt(1)), |
| instr->deopt_id()), |
| instr->env(), |
| Definition::kEffect); |
| needs_store_barrier = kNoStoreBarrier; |
| } |
| |
| if (field.guarded_cid() != kDynamicCid) { |
| InsertBefore(instr, |
| new GuardFieldInstr(new Value(instr->ArgumentAt(1)), |
| field, |
| instr->deopt_id()), |
| instr->env(), |
| Definition::kEffect); |
| } |
| |
| // Field guard was detached. |
| StoreInstanceFieldInstr* store = new StoreInstanceFieldInstr( |
| field, |
| new Value(instr->ArgumentAt(0)), |
| new Value(instr->ArgumentAt(1)), |
| needs_store_barrier); |
| // Discard the environment from the original instruction because the store |
| // can't deoptimize. |
| instr->RemoveEnvironment(); |
| ReplaceCall(instr, store); |
| return true; |
| } |
| |
| |
| void FlowGraphOptimizer::HandleRelationalOp(RelationalOpInstr* comp) { |
| if (!comp->HasICData() || (comp->ic_data()->NumberOfChecks() == 0)) { |
| return; |
| } |
| const ICData& ic_data = *comp->ic_data(); |
| Instruction* instr = current_iterator()->Current(); |
| if (ic_data.NumberOfChecks() == 1) { |
| ASSERT(ic_data.HasOneTarget()); |
| if (HasOnlyTwoSmis(ic_data)) { |
| InsertBefore(instr, |
| new CheckSmiInstr(comp->left()->Copy(), comp->deopt_id()), |
| instr->env(), |
| Definition::kEffect); |
| InsertBefore(instr, |
| new CheckSmiInstr(comp->right()->Copy(), comp->deopt_id()), |
| instr->env(), |
| Definition::kEffect); |
| comp->set_operands_class_id(kSmiCid); |
| } else if (ShouldSpecializeForDouble(ic_data)) { |
| comp->set_operands_class_id(kDoubleCid); |
| } else if (HasTwoMintOrSmi(*comp->ic_data()) && |
| FlowGraphCompiler::SupportsUnboxedMints()) { |
| comp->set_operands_class_id(kMintCid); |
| } else { |
| ASSERT(comp->operands_class_id() == kIllegalCid); |
| } |
| } else if (HasTwoMintOrSmi(*comp->ic_data()) && |
| FlowGraphCompiler::SupportsUnboxedMints()) { |
| comp->set_operands_class_id(kMintCid); |
| } |
| } |
| |
| |
| void FlowGraphOptimizer::VisitRelationalOp(RelationalOpInstr* instr) { |
| HandleRelationalOp(instr); |
| } |
| |
| |
| bool FlowGraphOptimizer::CanStrictifyEqualityCompare( |
| EqualityCompareInstr* compare) { |
| // If one of the inputs is null this is a strict comparison. |
| if (compare->left()->BindsToConstantNull() || |
| compare->right()->BindsToConstantNull()) { |
| return true; |
| } |
| |
| if (compare->left()->Type()->IsNone()) { |
| return false; // We might be running prior to any type propagation passes. |
| } |
| |
| // Try resolving target function using propagated cid for the receiver. |
| // If receiver is either null or has default equality operator then |
| // we can convert such comparison to a strict one. |
| const intptr_t receiver_cid = |
| compare->left()->Type()->ToNullableCid(); |
| |
| if (receiver_cid == kDynamicCid) { |
| return false; |
| } |
| |
| const Class& receiver_class = Class::Handle( |
| Isolate::Current()->class_table()->At(receiver_cid)); |
| |
| // Resolve equality operator. |
| const Function& function = Function::Handle( |
| Resolver::ResolveDynamicForReceiverClass( |
| receiver_class, |
| Symbols::EqualOperator(), |
| 2, |
| 0)); |
| |
| if (function.IsNull()) { |
| return false; |
| } |
| |
| // Default equality operator declared on the Object class just calls |
| // identical. |
| return (Class::Handle(function.Owner()).id() == kInstanceCid); |
| } |
| |
| |
| template <typename T> |
| bool FlowGraphOptimizer::StrictifyEqualityCompare( |
| EqualityCompareInstr* compare, |
| T current_instruction) const { |
| if (CanStrictifyEqualityCompare(compare)) { |
| Token::Kind strict_kind = (compare->kind() == Token::kEQ) ? |
| Token::kEQ_STRICT : Token::kNE_STRICT; |
| StrictCompareInstr* strict_comp = |
| new StrictCompareInstr(strict_kind, |
| compare->left()->CopyWithType(), |
| compare->right()->CopyWithType()); |
| current_instruction->ReplaceWith(strict_comp, current_iterator()); |
| return true; |
| } |
| return false; |
| } |
| |
| |
| template <typename T> |
| void FlowGraphOptimizer::HandleEqualityCompare(EqualityCompareInstr* comp, |
| T current_instruction) { |
| if (StrictifyEqualityCompare(comp, current_instruction)) { |
| return; |
| } |
| |
| if (!comp->HasICData() || (comp->ic_data()->NumberOfChecks() == 0)) { |
| return; |
| } |
| |
| ASSERT(comp->ic_data()->num_args_tested() == 2); |
| if (comp->ic_data()->NumberOfChecks() == 1) { |
| GrowableArray<intptr_t> class_ids; |
| Function& target = Function::Handle(); |
| comp->ic_data()->GetCheckAt(0, &class_ids, &target); |
| // TODO(srdjan): allow for mixed mode int/double comparison. |
| |
| if ((class_ids[0] == kSmiCid) && (class_ids[1] == kSmiCid)) { |
| InsertBefore(current_instruction, |
| new CheckSmiInstr(comp->left()->Copy(), comp->deopt_id()), |
| current_instruction->env(), |
| Definition::kEffect); |
| InsertBefore(current_instruction, |
| new CheckSmiInstr(comp->right()->Copy(), comp->deopt_id()), |
| current_instruction->env(), |
| Definition::kEffect); |
| comp->set_receiver_class_id(kSmiCid); |
| } else if ((class_ids[0] == kDoubleCid) && (class_ids[1] == kDoubleCid)) { |
| comp->set_receiver_class_id(kDoubleCid); |
| } else if (HasTwoMintOrSmi(*comp->ic_data()) && |
| FlowGraphCompiler::SupportsUnboxedMints()) { |
| comp->set_receiver_class_id(kMintCid); |
| } else { |
| ASSERT(comp->receiver_class_id() == kIllegalCid); |
| } |
| } else if (HasTwoMintOrSmi(*comp->ic_data()) && |
| FlowGraphCompiler::SupportsUnboxedMints()) { |
| comp->set_receiver_class_id(kMintCid); |
| } |
| |
| if (comp->receiver_class_id() != kIllegalCid) { |
| // Done. |
| return; |
| } |
| |
| // Check if ICDData contains checks with Smi/Null combinations. In that case |
| // we can still emit the optimized Smi equality operation but need to add |
| // checks for null or Smi. |
| // TODO(srdjan): Add it for Double and Mint. |
| GrowableArray<intptr_t> smi_or_null(2); |
| smi_or_null.Add(kSmiCid); |
| smi_or_null.Add(kNullCid); |
| if (ICDataHasOnlyReceiverArgumentClassIds(*comp->ic_data(), |
| smi_or_null, |
| smi_or_null)) { |
| const ICData& unary_checks_0 = |
| ICData::ZoneHandle(comp->ic_data()->AsUnaryClassChecks()); |
| AddCheckClass(comp->left()->definition(), |
| unary_checks_0, |
| comp->deopt_id(), |
| current_instruction->env(), |
| current_instruction); |
| |
| const ICData& unary_checks_1 = |
| ICData::ZoneHandle(comp->ic_data()->AsUnaryClassChecksForArgNr(1)); |
| AddCheckClass(comp->right()->definition(), |
| unary_checks_1, |
| comp->deopt_id(), |
| current_instruction->env(), |
| current_instruction); |
| comp->set_receiver_class_id(kSmiCid); |
| } |
| } |
| |
| |
| |
| |
| void FlowGraphOptimizer::VisitEqualityCompare(EqualityCompareInstr* instr) { |
| HandleEqualityCompare(instr, instr); |
| } |
| |
| |
| void FlowGraphOptimizer::VisitBranch(BranchInstr* instr) { |
| ComparisonInstr* comparison = instr->comparison(); |
| if (comparison->IsRelationalOp()) { |
| HandleRelationalOp(comparison->AsRelationalOp()); |
| } else if (comparison->IsEqualityCompare()) { |
| HandleEqualityCompare(comparison->AsEqualityCompare(), instr); |
| } else { |
| ASSERT(comparison->IsStrictCompare()); |
| // Nothing to do. |
| } |
| } |
| |
| |
| static bool MayBeBoxableNumber(intptr_t cid) { |
| return (cid == kDynamicCid) || |
| (cid == kMintCid) || |
| (cid == kBigintCid) || |
| (cid == kDoubleCid); |
| } |
| |
| |
| // Check if number check is not needed. |
| void FlowGraphOptimizer::VisitStrictCompare(StrictCompareInstr* instr) { |
| if (!instr->needs_number_check()) return; |
| |
| // If one of the input is not a boxable number (Mint, Double, Bigint), no |
| // need for number checks. |
| if (!MayBeBoxableNumber(instr->left()->Type()->ToCid()) || |
| !MayBeBoxableNumber(instr->right()->Type()->ToCid())) { |
| instr->set_needs_number_check(false); |
| } |
| } |
| |
| |
| // Range analysis for smi values. |
| class RangeAnalysis : public ValueObject { |
| public: |
| explicit RangeAnalysis(FlowGraph* flow_graph) |
| : flow_graph_(flow_graph), |
| marked_defns_(NULL) { } |
| |
| // Infer ranges for all values and remove overflow checks from binary smi |
| // operations when proven redundant. |
| void Analyze(); |
| |
| private: |
| // Collect all values that were proven to be smi in smi_values_ array and all |
| // CheckSmi instructions in smi_check_ array. |
| void CollectSmiValues(); |
| |
| // Iterate over smi values and constrain them at branch successors. |
| // Additionally constraint values after CheckSmi instructions. |
| void InsertConstraints(); |
| |
| // Iterate over uses of the given definition and discover branches that |
| // constrain it. Insert appropriate Constraint instructions at true |
| // and false successor and rename all dominated uses to refer to a |
| // Constraint instead of this definition. |
| void InsertConstraintsFor(Definition* defn); |
| |
| // Create a constraint for defn, insert it after given instruction and |
| // rename all uses that are dominated by it. |
| ConstraintInstr* InsertConstraintFor(Definition* defn, |
| Range* constraint, |
| Instruction* after); |
| |
| void ConstrainValueAfterBranch(Definition* defn, Value* use); |
| void ConstrainValueAfterCheckArrayBound(Definition* defn, |
| CheckArrayBoundInstr* check); |
| |
| // Replace uses of the definition def that are dominated by instruction dom |
| // with uses of other definition. |
| void RenameDominatedUses(Definition* def, |
| Instruction* dom, |
| Definition* other); |
| |
| |
| // Walk the dominator tree and infer ranges for smi values. |
| void InferRanges(); |
| void InferRangesRecursive(BlockEntryInstr* block); |
| |
| enum Direction { |
| kUnknown, |
| kPositive, |
| kNegative, |
| kBoth |
| }; |
| |
| Range* InferInductionVariableRange(JoinEntryInstr* loop_header, |
| PhiInstr* var); |
| |
| void ResetWorklist(); |
| void MarkDefinition(Definition* defn); |
| |
| static Direction ToDirection(Value* val); |
| |
| static Direction Invert(Direction direction) { |
| return (direction == kPositive) ? kNegative : kPositive; |
| } |
| |
| static void UpdateDirection(Direction* direction, |
| Direction new_direction) { |
| if (*direction != new_direction) { |
| if (*direction != kUnknown) new_direction = kBoth; |
| *direction = new_direction; |
| } |
| } |
| |
| // Remove artificial Constraint instructions and replace them with actual |
| // unconstrained definitions. |
| void RemoveConstraints(); |
| |
| FlowGraph* flow_graph_; |
| |
| GrowableArray<Definition*> smi_values_; // Value that are known to be smi. |
| GrowableArray<CheckSmiInstr*> smi_checks_; // All CheckSmi instructions. |
| |
| // All Constraints inserted during InsertConstraints phase. They are treated |
| // as smi values. |
| GrowableArray<ConstraintInstr*> constraints_; |
| |
| // Bitvector for a quick filtering of known smi values. |
| BitVector* smi_definitions_; |
| |
| // Worklist for induction variables analysis. |
| GrowableArray<Definition*> worklist_; |
| BitVector* marked_defns_; |
| |
| DISALLOW_COPY_AND_ASSIGN(RangeAnalysis); |
| }; |
| |
| |
| void RangeAnalysis::Analyze() { |
| CollectSmiValues(); |
| InsertConstraints(); |
| InferRanges(); |
| RemoveConstraints(); |
| } |
| |
| |
| void RangeAnalysis::CollectSmiValues() { |
| 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) { |
| if ((defn->Type()->ToCid() == kSmiCid) && |
| (defn->ssa_temp_index() != -1)) { |
| smi_values_.Add(defn); |
| } |
| } else if (current->IsCheckSmi()) { |
| smi_checks_.Add(current->AsCheckSmi()); |
| } |
| } |
| |
| JoinEntryInstr* join = block->AsJoinEntry(); |
| if (join != NULL) { |
| for (PhiIterator phi_it(join); !phi_it.Done(); phi_it.Advance()) { |
| PhiInstr* current = phi_it.Current(); |
| if ((current->Type()->ToCid() == kSmiCid)) { |
| smi_values_.Add(current); |
| } |
| } |
| } |
| } |
| } |
| |
| |
| // Returns true if use is dominated by the given instruction. |
| // Note: uses that occur at instruction itself are not dominated by it. |
| static bool IsDominatedUse(Instruction* dom, Value* use) { |
| BlockEntryInstr* dom_block = dom->GetBlock(); |
| |
| Instruction* instr = use->instruction(); |
| |
| PhiInstr* phi = instr->AsPhi(); |
| if (phi != NULL) { |
| return dom_block->Dominates(phi->block()->PredecessorAt(use->use_index())); |
| } |
| |
| BlockEntryInstr* use_block = instr->GetBlock(); |
| if (use_block == dom_block) { |
| // Fast path for the case of block entry. |
| if (dom_block == dom) return true; |
| |
| for (Instruction* curr = dom->next(); curr != NULL; curr = curr->next()) { |
| if (curr == instr) return true; |
| } |
| |
| return false; |
| } |
| |
| return dom_block->Dominates(use_block); |
| } |
| |
| |
| void RangeAnalysis::RenameDominatedUses(Definition* def, |
| Instruction* dom, |
| Definition* other) { |
| for (Value::Iterator it(def->input_use_list()); |
| !it.Done(); |
| it.Advance()) { |
| Value* use = it.Current(); |
| |
| // Skip dead phis. |
| PhiInstr* phi = use->instruction()->AsPhi(); |
| ASSERT((phi == NULL) || phi->is_alive()); |
| if (IsDominatedUse(dom, use)) { |
| use->BindTo(other); |
| } |
| } |
| } |
| |
| |
| // For a comparison operation return an operation for the equivalent flipped |
| // comparison: a (op) b === b (op') a. |
| static Token::Kind FlipComparison(Token::Kind op) { |
| switch (op) { |
| case Token::kEQ: return Token::kEQ; |
| case Token::kNE: return Token::kNE; |
| case Token::kLT: return Token::kGT; |
| case Token::kGT: return Token::kLT; |
| case Token::kLTE: return Token::kGTE; |
| case Token::kGTE: return Token::kLTE; |
| default: |
| UNREACHABLE(); |
| return Token::kILLEGAL; |
| } |
| } |
| |
| |
| // Given a boundary (right operand) and a comparison operation return |
| // a symbolic range constraint for the left operand of the comparison assuming |
| // that it evaluated to true. |
| // For example for the comparison a < b symbol a is constrained with range |
| // [Smi::kMinValue, b - 1]. |
| static Range* ConstraintRange(Token::Kind op, Definition* boundary) { |
| switch (op) { |
| case Token::kEQ: |
| return new Range(RangeBoundary::FromDefinition(boundary), |
| RangeBoundary::FromDefinition(boundary)); |
| case Token::kNE: |
| return Range::Unknown(); |
| case Token::kLT: |
| return new Range(RangeBoundary::MinSmi(), |
| RangeBoundary::FromDefinition(boundary, -1)); |
| case Token::kGT: |
| return new Range(RangeBoundary::FromDefinition(boundary, 1), |
| RangeBoundary::MaxSmi()); |
| case Token::kLTE: |
| return new Range(RangeBoundary::MinSmi(), |
| RangeBoundary::FromDefinition(boundary)); |
| case Token::kGTE: |
| return new Range(RangeBoundary::FromDefinition(boundary), |
| RangeBoundary::MaxSmi()); |
| default: |
| UNREACHABLE(); |
| return Range::Unknown(); |
| } |
| } |
| |
| |
| ConstraintInstr* RangeAnalysis::InsertConstraintFor(Definition* defn, |
| Range* constraint_range, |
| Instruction* after) { |
| // No need to constrain constants. |
| if (defn->IsConstant()) return NULL; |
| |
| ConstraintInstr* constraint = |
| new ConstraintInstr(new Value(defn), constraint_range); |
| flow_graph_->InsertAfter(after, constraint, NULL, Definition::kValue); |
| RenameDominatedUses(defn, constraint, constraint); |
| constraints_.Add(constraint); |
| return constraint; |
| } |
| |
| |
| void RangeAnalysis::ConstrainValueAfterBranch(Definition* defn, Value* use) { |
| BranchInstr* branch = use->instruction()->AsBranch(); |
| RelationalOpInstr* rel_op = branch->comparison()->AsRelationalOp(); |
| if ((rel_op != NULL) && (rel_op->operands_class_id() == kSmiCid)) { |
| // Found comparison of two smis. Constrain defn at true and false |
| // successors using the other operand as a boundary. |
| Definition* boundary; |
| Token::Kind op_kind; |
| if (use->use_index() == 0) { // Left operand. |
| boundary = rel_op->InputAt(1)->definition(); |
| op_kind = rel_op->kind(); |
| } else { |
| ASSERT(use->use_index() == 1); // Right operand. |
| boundary = rel_op->InputAt(0)->definition(); |
| // InsertConstraintFor assumes that defn is left operand of a |
| // comparison if it is right operand flip the comparison. |
| op_kind = FlipComparison(rel_op->kind()); |
| } |
| |
| // Constrain definition at the true successor. |
| ConstraintInstr* true_constraint = |
| InsertConstraintFor(defn, |
| ConstraintRange(op_kind, boundary), |
| branch->true_successor()); |
| // Mark true_constraint an artificial use of boundary. This ensures |
| // that constraint's range is recalculated if boundary's range changes. |
| if (true_constraint != NULL) { |
| true_constraint->AddDependency(boundary); |
| true_constraint->set_target(branch->true_successor()); |
| } |
| |
| // Constrain definition with a negated condition at the false successor. |
| ConstraintInstr* false_constraint = |
| InsertConstraintFor( |
| defn, |
| ConstraintRange(Token::NegateComparison(op_kind), boundary), |
| branch->false_successor()); |
| // Mark false_constraint an artificial use of boundary. This ensures |
| // that constraint's range is recalculated if boundary's range changes. |
| if (false_constraint != NULL) { |
| false_constraint->AddDependency(boundary); |
| false_constraint->set_target(branch->false_successor()); |
| } |
| } |
| } |
| |
| void RangeAnalysis::InsertConstraintsFor(Definition* defn) { |
| for (Value* use = defn->input_use_list(); |
| use != NULL; |
| use = use->next_use()) { |
| if (use->instruction()->IsBranch()) { |
| ConstrainValueAfterBranch(defn, use); |
| } else if (use->instruction()->IsCheckArrayBound()) { |
| ConstrainValueAfterCheckArrayBound( |
| defn, |
| use->instruction()->AsCheckArrayBound()); |
| } |
| } |
| } |
| |
| |
| void RangeAnalysis::ConstrainValueAfterCheckArrayBound( |
| Definition* defn, CheckArrayBoundInstr* check) { |
| if (!CheckArrayBoundInstr::IsFixedLengthArrayType(check->array_type())) { |
| return; |
| } |
| |
| Definition* length = check->length()->definition(); |
| |
| Range* constraint_range = new Range( |
| RangeBoundary::FromConstant(0), |
| RangeBoundary::FromDefinition(length, -1)); |
| InsertConstraintFor(defn, constraint_range, check); |
| } |
| |
| |
| void RangeAnalysis::InsertConstraints() { |
| for (intptr_t i = 0; i < smi_checks_.length(); i++) { |
| CheckSmiInstr* check = smi_checks_[i]; |
| InsertConstraintFor(check->value()->definition(), Range::Unknown(), check); |
| } |
| |
| for (intptr_t i = 0; i < smi_values_.length(); i++) { |
| InsertConstraintsFor(smi_values_[i]); |
| } |
| |
| for (intptr_t i = 0; i < constraints_.length(); i++) { |
| InsertConstraintsFor(constraints_[i]); |
| } |
| } |
| |
| |
| void RangeAnalysis::ResetWorklist() { |
| if (marked_defns_ == NULL) { |
| marked_defns_ = new BitVector(flow_graph_->current_ssa_temp_index()); |
| } else { |
| marked_defns_->Clear(); |
| } |
| worklist_.Clear(); |
| } |
| |
| |
| void RangeAnalysis::MarkDefinition(Definition* defn) { |
| // Unwrap constrained value. |
| while (defn->IsConstraint()) { |
| defn = defn->AsConstraint()->value()->definition(); |
| } |
| |
| if (!marked_defns_->Contains(defn->ssa_temp_index())) { |
| worklist_.Add(defn); |
| marked_defns_->Add(defn->ssa_temp_index()); |
| } |
| } |
| |
| |
| RangeAnalysis::Direction RangeAnalysis::ToDirection(Value* val) { |
| if (val->BindsToConstant()) { |
| return (Smi::Cast(val->BoundConstant()).Value() >= 0) ? kPositive |
| : kNegative; |
| } else if (val->definition()->range() != NULL) { |
| Range* range = val->definition()->range(); |
| if (Range::ConstantMin(range).value() >= 0) { |
| return kPositive; |
| } else if (Range::ConstantMax(range).value() <= 0) { |
| return kNegative; |
| } |
| } |
| return kUnknown; |
| } |
| |
| |
| Range* RangeAnalysis::InferInductionVariableRange(JoinEntryInstr* loop_header, |
| PhiInstr* var) { |
| BitVector* loop_info = loop_header->loop_info(); |
| |
| Definition* initial_value = NULL; |
| Direction direction = kUnknown; |
| |
| ResetWorklist(); |
| MarkDefinition(var); |
| while (!worklist_.is_empty()) { |
| Definition* defn = worklist_.RemoveLast(); |
| |
| if (defn->IsPhi()) { |
| PhiInstr* phi = defn->AsPhi(); |
| for (intptr_t i = 0; i < phi->InputCount(); i++) { |
| Definition* defn = phi->InputAt(i)->definition(); |
| |
| if (!loop_info->Contains(defn->GetBlock()->preorder_number())) { |
| // The value is coming from outside of the loop. |
| if (initial_value == NULL) { |
| initial_value = defn; |
| continue; |
| } else if (initial_value == defn) { |
| continue; |
| } else { |
| return NULL; |
| } |
| } |
| |
| MarkDefinition(defn); |
| } |
| } else if (defn->IsBinarySmiOp()) { |
| BinarySmiOpInstr* binary_op = defn->AsBinarySmiOp(); |
| |
| switch (binary_op->op_kind()) { |
| case Token::kADD: { |
| const Direction growth_right = |
| ToDirection(binary_op->right()); |
| if (growth_right != kUnknown) { |
| UpdateDirection(&direction, growth_right); |
| MarkDefinition(binary_op->left()->definition()); |
| break; |
| } |
| |
| const Direction growth_left = |
| ToDirection(binary_op->left()); |
| if (growth_left != kUnknown) { |
| UpdateDirection(&direction, growth_left); |
| MarkDefinition(binary_op->right()->definition()); |
| break; |
| } |
| |
| return NULL; |
| } |
| |
| case Token::kSUB: { |
| const Direction growth_right = |
| ToDirection(binary_op->right()); |
| if (growth_right != kUnknown) { |
| UpdateDirection(&direction, Invert(growth_right)); |
| MarkDefinition(binary_op->left()->definition()); |
| break; |
| } |
| return NULL; |
| } |
| |
| default: |
| return NULL; |
| } |
| } else { |
| return NULL; |
| } |
| } |
| |
| |
| // We transitively discovered all dependencies of the given phi |
| // and confirmed that it depends on a single value coming from outside of |
| // the loop and some linear combinations of itself. |
| // Compute the range based on initial value and the direction of the growth. |
| switch (direction) { |
| case kPositive: |
| return new Range(RangeBoundary::FromDefinition(initial_value), |
| RangeBoundary::MaxSmi()); |
| |
| case kNegative: |
| return new Range(RangeBoundary::MinSmi(), |
| RangeBoundary::FromDefinition(initial_value)); |
| |
| case kUnknown: |
| case kBoth: |
| return Range::Unknown(); |
| } |
| |
| UNREACHABLE(); |
| return NULL; |
| } |
| |
| |
| void RangeAnalysis::InferRangesRecursive(BlockEntryInstr* block) { |
| 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) { |
| phi->range_ = range; |
| continue; |
| } |
| } |
| |
| phi->InferRange(); |
| } |
| } |
| } |
| |
| for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
| Instruction* current = it.Current(); |
| |
| Definition* defn = current->AsDefinition(); |
| if ((defn != NULL) && |
| (defn->ssa_temp_index() != -1) && |
| smi_definitions_->Contains(defn->ssa_temp_index())) { |
| defn->InferRange(); |
| } else if (FLAG_array_bounds_check_elimination && |
| current->IsCheckArrayBound()) { |
| CheckArrayBoundInstr* check = current->AsCheckArrayBound(); |
| RangeBoundary array_length = |
| RangeBoundary::FromDefinition(check->length()->definition()); |
| if (check->IsRedundant(array_length)) { |
| it.RemoveCurrentFromGraph(); |
| } |
| } |
| } |
| |
| for (intptr_t i = 0; i < block->dominated_blocks().length(); ++i) { |
| InferRangesRecursive(block->dominated_blocks()[i]); |
| } |
| } |
| |
| |
| void RangeAnalysis::InferRanges() { |
| // Initialize bitvector for quick filtering of smi values. |
| smi_definitions_ = new BitVector(flow_graph_->current_ssa_temp_index()); |
| for (intptr_t i = 0; i < smi_values_.length(); i++) { |
| smi_definitions_->Add(smi_values_[i]->ssa_temp_index()); |
| } |
| for (intptr_t i = 0; i < constraints_.length(); i++) { |
| smi_definitions_->Add(constraints_[i]->ssa_temp_index()); |
| } |
| |
| // Infer initial values of ranges. |
| InferRangesRecursive(flow_graph_->graph_entry()); |
| |
| if (FLAG_trace_range_analysis) { |
| OS::Print("---- after range analysis -------\n"); |
| FlowGraphPrinter printer(*flow_graph_); |
| printer.PrintBlocks(); |
| } |
| } |
| |
| |
| void RangeAnalysis::RemoveConstraints() { |
| for (intptr_t i = 0; i < constraints_.length(); i++) { |
| Definition* def = constraints_[i]->value()->definition(); |
| // Some constraints might be constraining constraints. Unwind the chain of |
| // constraints until we reach the actual definition. |
| while (def->IsConstraint()) { |
| def = def->AsConstraint()->value()->definition(); |
| } |
| constraints_[i]->ReplaceUsesWith(def); |
| constraints_[i]->RemoveFromGraph(); |
| } |
| } |
| |
| |
| void FlowGraphOptimizer::InferSmiRanges() { |
| RangeAnalysis range_analysis(flow_graph_); |
| range_analysis.Analyze(); |
| } |
| |
| |
| 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; |
| } |
| |
| |
| LICM::LICM(FlowGraph* flow_graph) : flow_graph_(flow_graph) { |
| } |
| |
| |
| void LICM::Hoist(ForwardInstructionIterator* it, |
| BlockEntryInstr* pre_header, |
| Instruction* current) { |
| // TODO(fschneider): Avoid repeated deoptimization when |
| // speculatively hoisting checks. |
| if (FLAG_trace_optimization) { |
| OS::Print("Hoisting instruction %s:%"Pd" from B%"Pd" to B%"Pd"\n", |
| current->DebugName(), |
| current->GetDeoptId(), |
| current->GetBlock()->block_id(), |
| pre_header->block_id()); |
| } |
| // Move the instruction out of the loop. |
| current->RemoveEnvironment(); |
| it->RemoveCurrentFromGraph(); |
| GotoInstr* last = pre_header->last_instruction()->AsGoto(); |
| // Using kind kEffect will not assign a fresh ssa temporary index. |
| flow_graph()->InsertBefore(last, current, last->env(), Definition::kEffect); |
| current->deopt_id_ = last->GetDeoptId(); |
| } |
| |
| |
| void LICM::TryHoistCheckSmiThroughPhi(ForwardInstructionIterator* it, |
| BlockEntryInstr* header, |
| BlockEntryInstr* pre_header, |
| CheckSmiInstr* current) { |
| PhiInstr* phi = current->value()->definition()->AsPhi(); |
| if (!header->loop_info()->Contains(phi->block()->preorder_number())) { |
| return; |
| } |
| |
| if (phi->Type()->ToCid() == kSmiCid) { |
| it->RemoveCurrentFromGraph(); |
| return; |
| } |
| |
| // Check if there is only a single kDynamicCid input to the phi that |
| // comes from the pre-header. |
| const intptr_t kNotFound = -1; |
| intptr_t non_smi_input = kNotFound; |
| for (intptr_t i = 0; i < phi->InputCount(); ++i) { |
| Value* input = phi->InputAt(i); |
| 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; |
| } else { |
| non_smi_input = i; |
| } |
| } |
| } |
| |
| if ((non_smi_input == kNotFound) || |
| (phi->block()->PredecessorAt(non_smi_input) != pre_header)) { |
| return; |
| } |
| |
| // Host CheckSmi instruction and make this phi smi one. |
| Hoist(it, pre_header, current); |
| |
| // Replace value we are checking with phi's input. |
| current->value()->BindTo(phi->InputAt(non_smi_input)->definition()); |
| |
| phi->UpdateType(CompileType::FromCid(kSmiCid)); |
| } |
| |
| |
| void LICM::Optimize() { |
| GrowableArray<BlockEntryInstr*> loop_headers; |
| flow_graph()->ComputeLoops(&loop_headers); |
| |
| for (intptr_t i = 0; i < loop_headers.length(); ++i) { |
| BlockEntryInstr* header = loop_headers[i]; |
| // Skip loop that don't have a pre-header block. |
| BlockEntryInstr* pre_header = FindPreHeader(header); |
| if (pre_header == NULL) continue; |
| |
| for (BitVector::Iterator loop_it(header->loop_info()); |
| !loop_it.Done(); |
| loop_it.Advance()) { |
| BlockEntryInstr* block = flow_graph()->preorder()[loop_it.Current()]; |
| for (ForwardInstructionIterator it(block); |
| !it.Done(); |
| it.Advance()) { |
| Instruction* current = it.Current(); |
| if (!current->IsPushArgument() && |
| current->AllowsCSE() && |
| flow_graph()->block_effects()->CanBeMovedTo(current, pre_header)) { |
| bool inputs_loop_invariant = true; |
| for (int i = 0; i < current->InputCount(); ++i) { |
| Definition* input_def = current->InputAt(i)->definition(); |
| if (!input_def->GetBlock()->Dominates(pre_header)) { |
| inputs_loop_invariant = false; |
| break; |
| } |
| } |
| if (inputs_loop_invariant && |
| !current->IsAssertAssignable() && |
| !current->IsAssertBoolean()) { |
| // TODO(fschneider): Enable hoisting of Assert-instructions |
| // if it safe to do. |
| Hoist(&it, pre_header, current); |
| } else if (current->IsCheckSmi() && |
| current->InputAt(0)->definition()->IsPhi()) { |
| TryHoistCheckSmiThroughPhi( |
| &it, header, pre_header, current->AsCheckSmi()); |
| } |
| } |
| } |
| } |
| } |
| } |
| |
| |
| static bool IsLoadEliminationCandidate(Definition* def) { |
| // Immutable loads (not affected by side effects) are handled |
| // in the DominatorBasedCSE pass. |
| // TODO(fschneider): Extend to other load instructions. |
| return (def->IsLoadField() && !def->Dependencies().IsNone()) |
| || def->IsLoadIndexed() |
| || def->IsLoadStaticField() |
| || def->IsCurrentContext(); |
| } |
| |
| |
| // Alias represents a family of locations. It is used to capture aliasing |
| // between stores and loads. Store can alias another load or store if and only |
| // if they have the same alias. |
| class Alias : public ValueObject { |
| public: |
| Alias(const Alias& other) : ValueObject(), alias_(other.alias_) { } |
| |
| // All indexed load/stores alias each other. |
| // TODO(vegorov): incorporate type of array into alias to disambiguate |
| // different typed data and normal arrays. |
| static Alias Indexes() { |
| return Alias(kIndexesAlias); |
| } |
| |
| // Field load/stores alias each other when field offset matches. |
| // TODO(vegorov): use field information to disambiguate load/stores into |
| // different fields that by accident share offset. |
| static Alias Field(intptr_t offset_in_bytes) { |
| const intptr_t idx = offset_in_bytes / kWordSize; |
| ASSERT(idx >= kFirstFieldAlias); |
| return Alias(idx * 2); |
| } |
| |
| // Static field load/stores alias each other. |
| // AliasedSet assigns ids to static fields during optimization phase. |
| static Alias StaticField(intptr_t id) { |
| ASSERT(id >= kFirstFieldAlias); |
| return Alias(id * 2 + 1); |
| } |
| |
| // Current context load/stores alias each other. |
| static Alias CurrentContext() { |
| return Alias(kCurrentContextAlias); |
| } |
| |
| // Operation does not alias anything. |
| static Alias None() { |
| return Alias(kNoneAlias); |
| } |
| |
| bool IsNone() const { |
| return alias_ == kNoneAlias; |
| } |
| |
| // Convert this alias to a positive array index. |
| intptr_t ToIndex() const { |
| ASSERT(!IsNone()); |
| return alias_ - kAliasBase; |
| } |
| |
| private: |
| explicit Alias(intptr_t alias) : alias_(alias) { } |
| |
| enum { |
| kNoneAlias = -2, |
| kCurrentContextAlias = -1, |
| kIndexesAlias = 0, |
| kFirstFieldAlias = kIndexesAlias + 1, |
| kAliasBase = kCurrentContextAlias |
| }; |
| |
| const intptr_t alias_; |
| }; |
| |
| |
| // Set mapping alias to a list of loads sharing this alias. |
| class AliasedSet : public ZoneAllocated { |
| public: |
| explicit AliasedSet(intptr_t max_expr_id) |
| : max_expr_id_(max_expr_id), |
| sets_(), |
| field_ids_(), |
| max_field_id_(0) { } |
| |
| Alias ComputeAliasForLoad(Definition* defn) { |
| if (defn->IsLoadIndexed()) { |
| // We are assuming that LoadField is never used to load the first word. |
| return Alias::Indexes(); |
| } |
| |
| LoadFieldInstr* load_field = defn->AsLoadField(); |
| if (load_field != NULL) { |
| return Alias::Field(load_field->offset_in_bytes()); |
| } |
| |
| if (defn->IsCurrentContext()) { |
| return Alias::CurrentContext(); |
| } |
| |
| LoadStaticFieldInstr* load_static_field = defn->AsLoadStaticField(); |
| if (load_static_field != NULL) { |
| return Alias::StaticField(GetFieldId(load_static_field->field())); |
| } |
| |
| UNREACHABLE(); |
| return Alias::None(); |
| } |
| |
| Alias ComputeAliasForStore(Instruction* instr) { |
| if (instr->IsStoreIndexed()) { |
| return Alias::Indexes(); |
| } |
| |
| StoreInstanceFieldInstr* store_instance_field = |
| instr->AsStoreInstanceField(); |
| if (store_instance_field != NULL) { |
| return Alias::Field(store_instance_field->field().Offset()); |
| } |
| |
| StoreVMFieldInstr* store_vm_field = instr->AsStoreVMField(); |
| if (store_vm_field != NULL) { |
| return Alias::Field(store_vm_field->offset_in_bytes()); |
| } |
| |
| if (instr->IsStoreContext() || instr->IsChainContext()) { |
| return Alias::CurrentContext(); |
| } |
| |
| StoreStaticFieldInstr* store_static_field = instr->AsStoreStaticField(); |
| if (store_static_field != NULL) { |
| return Alias::StaticField(GetFieldId(store_static_field->field())); |
| } |
| |
| return Alias::None(); |
| } |
| |
| bool Contains(const Alias alias) { |
| const intptr_t idx = alias.ToIndex(); |
| return (idx < sets_.length()) && (sets_[idx] != NULL); |
| } |
| |
| BitVector* Get(const Alias alias) { |
| ASSERT(Contains(alias)); |
| return sets_[alias.ToIndex()]; |
| } |
| |
| void Add(const Alias alias, intptr_t ssa_index) { |
| const intptr_t idx = alias.ToIndex(); |
| |
| while (sets_.length() <= idx) { |
| sets_.Add(NULL); |
| } |
| |
| if (sets_[idx] == NULL) { |
| sets_[idx] = new BitVector(max_expr_id_); |
| } |
| |
| sets_[idx]->Add(ssa_index); |
| } |
| |
| intptr_t max_expr_id() const { return max_expr_id_; } |
| bool IsEmpty() const { return max_expr_id_ == 0; } |
| |
| private: |
| const intptr_t max_expr_id_; |
| |
| // Maps alias index to a set of ssa indexes corresponding to loads with the |
| // given alias. |
| GrowableArray<BitVector*> sets_; |
| |
| // Get id assigned to the given field. Assign a new id if the field is seen |
| // for the first time. |
| intptr_t GetFieldId(const Field& field) { |
| intptr_t id = field_ids_.Lookup(&field); |
| if (id == 0) { |
| id = ++max_field_id_; |
| field_ids_.Insert(FieldIdPair(&field, id)); |
| } |
| return id; |
| } |
| |
| class FieldIdPair { |
| public: |
| typedef const Field* Key; |
| typedef intptr_t Value; |
| typedef FieldIdPair Pair; |
| |
| FieldIdPair(Key key, Value value) : key_(key), value_(value) { } |
| |
| static Key KeyOf(Pair kv) { |
| return kv.key_; |
| } |
| |
| static Value ValueOf(Pair kv) { |
| return kv.value_; |
| } |
| |
| static intptr_t Hashcode(Key key) { |
| return String::Handle(key->name()).Hash(); |
| } |
| |
| static inline bool IsKeyEqual(Pair kv, Key key) { |
| return KeyOf(kv)->raw() == key->raw(); |
| } |
| |
| private: |
| Key key_; |
| Value value_; |
| }; |
| |
| // Table mapping static field to their id used during optimization pass. |
| DirectChainedHashMap<FieldIdPair> field_ids_; |
| intptr_t max_field_id_; |
| }; |
| |
| |
| static Definition* GetStoredValue(Instruction* instr) { |
| if (instr->IsStoreIndexed()) { |
| return instr->AsStoreIndexed()->value()->definition(); |
| } |
| |
| StoreInstanceFieldInstr* store_instance_field = instr->AsStoreInstanceField(); |
| if (store_instance_field != NULL) { |
| return store_instance_field->value()->definition(); |
| } |
| |
| StoreVMFieldInstr* store_vm_field = instr->AsStoreVMField(); |
| if (store_vm_field != NULL) { |
| return store_vm_field->value()->definition(); |
| } |
| |
| StoreStaticFieldInstr* store_static_field = instr->AsStoreStaticField(); |
| if (store_static_field != NULL) { |
| return store_static_field->value()->definition(); |
| } |
| |
| if (instr->IsStoreContext() || instr->IsChainContext()) { |
| return instr->InputAt(0)->definition(); |
| } |
| |
| UNREACHABLE(); // Should only be called for supported store instructions. |
| return NULL; |
| } |
| |
| |
| // KeyValueTrait used for numbering of loads. Allows to lookup loads |
| // corresponding to stores. |
| class LoadKeyValueTrait { |
| public: |
| typedef Definition* Value; |
| typedef Instruction* Key; |
| typedef Definition* Pair; |
| |
| static Key KeyOf(Pair kv) { |
| return kv; |
| } |
| |
| static Value ValueOf(Pair kv) { |
| return kv; |
| } |
| |
| static inline intptr_t Hashcode(Key key) { |
| intptr_t object = 0; |
| intptr_t location = 0; |
| |
| if (key->IsLoadIndexed()) { |
| LoadIndexedInstr* load_indexed = key->AsLoadIndexed(); |
| object = load_indexed->array()->definition()->ssa_temp_index(); |
| location = load_indexed->index()->definition()->ssa_temp_index(); |
| } else if (key->IsStoreIndexed()) { |
| StoreIndexedInstr* store_indexed = key->AsStoreIndexed(); |
| object = store_indexed->array()->definition()->ssa_temp_index(); |
| location = store_indexed->index()->definition()->ssa_temp_index(); |
| } else if (key->IsLoadField()) { |
| LoadFieldInstr* load_field = key->AsLoadField(); |
| object = load_field->value()->definition()->ssa_temp_index(); |
| location = load_field->offset_in_bytes(); |
| } else if (key->IsStoreInstanceField()) { |
| StoreInstanceFieldInstr* store_field = key->AsStoreInstanceField(); |
| object = store_field->instance()->definition()->ssa_temp_index(); |
| location = store_field->field().Offset(); |
| } else if (key->IsStoreVMField()) { |
| StoreVMFieldInstr* store_field = key->AsStoreVMField(); |
| object = store_field->dest()->definition()->ssa_temp_index(); |
| location = store_field->offset_in_bytes(); |
| } else if (key->IsLoadStaticField()) { |
| LoadStaticFieldInstr* load_static_field = key->AsLoadStaticField(); |
| object = String::Handle(load_static_field->field().name()).Hash(); |
| } else if (key->IsStoreStaticField()) { |
| StoreStaticFieldInstr* store_static_field = key->AsStoreStaticField(); |
| object = String::Handle(store_static_field->field().name()).Hash(); |
| } else { |
| ASSERT(key->IsStoreContext() || |
| key->IsCurrentContext() || |
| key->IsChainContext()); |
| } |
| |
| return object * 31 + location; |
| } |
| |
| static inline bool IsKeyEqual(Pair kv, Key key) { |
| if (kv->Equals(key)) return true; |
| |
| if (kv->IsLoadIndexed()) { |
| if (key->IsStoreIndexed()) { |
| LoadIndexedInstr* load_indexed = kv->AsLoadIndexed(); |
| StoreIndexedInstr* store_indexed = key->AsStoreIndexed(); |
| return load_indexed->array()->Equals(store_indexed->array()) && |
| load_indexed->index()->Equals(store_indexed->index()); |
| } |
| return false; |
| } |
| |
| if (kv->IsLoadStaticField()) { |
| if (key->IsStoreStaticField()) { |
| LoadStaticFieldInstr* load_static_field = kv->AsLoadStaticField(); |
| StoreStaticFieldInstr* store_static_field = key->AsStoreStaticField(); |
| return load_static_field->field().raw() == |
| store_static_field->field().raw(); |
| } |
| return false; |
| } |
| |
| if (kv->IsCurrentContext()) { |
| return key->IsStoreContext() || key->IsChainContext(); |
| } |
| |
| ASSERT(kv->IsLoadField()); |
| LoadFieldInstr* load_field = kv->AsLoadField(); |
| if (key->IsStoreVMField()) { |
| StoreVMFieldInstr* store_field = key->AsStoreVMField(); |
| return load_field->value()->Equals(store_field->dest()) && |
| (load_field->offset_in_bytes() == store_field->offset_in_bytes()); |
| } else if (key->IsStoreInstanceField()) { |
| StoreInstanceFieldInstr* store_field = key->AsStoreInstanceField(); |
| return load_field->value()->Equals(store_field->instance()) && |
| (load_field->offset_in_bytes() == store_field->field().Offset()); |
| } |
| |
| return false; |
| } |
| }; |
| |
| |
| static AliasedSet* NumberLoadExpressions( |
| FlowGraph* graph, |
| DirectChainedHashMap<LoadKeyValueTrait>* map) { |
| intptr_t expr_id = 0; |
| |
| // Loads representing different expression ids will be collected and |
| // used to build per offset kill sets. |
| GrowableArray<Definition*> loads(10); |
| |
| for (BlockIterator it = graph->reverse_postorder_iterator(); |
| !it.Done(); |
| it.Advance()) { |
| BlockEntryInstr* block = it.Current(); |
| for (ForwardInstructionIterator instr_it(block); |
| !instr_it.Done(); |
| instr_it.Advance()) { |
| Definition* defn = instr_it.Current()->AsDefinition(); |
| if ((defn == NULL) || !IsLoadEliminationCandidate(defn)) { |
| continue; |
| } |
| Definition* result = map->Lookup(defn); |
| if (result == NULL) { |
| map->Insert(defn); |
| defn->set_expr_id(expr_id++); |
| loads.Add(defn); |
| } else { |
| defn->set_expr_id(result->expr_id()); |
| } |
| } |
| } |
| |
| // Build aliasing sets mapping aliases to loads. |
| AliasedSet* aliased_set = new AliasedSet(expr_id); |
| for (intptr_t i = 0; i < loads.length(); i++) { |
| Definition* defn = loads[i]; |
| aliased_set->Add(aliased_set->ComputeAliasForLoad(defn), defn->expr_id()); |
| } |
| return aliased_set; |
| } |
| |
| |
| class LoadOptimizer : public ValueObject { |
| public: |
| LoadOptimizer(FlowGraph* graph, |
| AliasedSet* aliased_set, |
| DirectChainedHashMap<LoadKeyValueTrait>* map) |
| : graph_(graph), |
| map_(map), |
| aliased_set_(aliased_set), |
| in_(graph_->preorder().length()), |
| out_(graph_->preorder().length()), |
| gen_(graph_->preorder().length()), |
| kill_(graph_->preorder().length()), |
| exposed_values_(graph_->preorder().length()), |
| out_values_(graph_->preorder().length()), |
| phis_(5), |
| worklist_(5), |
| in_worklist_(NULL), |
| forwarded_(false) { |
| const intptr_t num_blocks = graph_->preorder().length(); |
| for (intptr_t i = 0; i < num_blocks; i++) { |
| out_.Add(new BitVector(aliased_set_->max_expr_id())); |
| gen_.Add(new BitVector(aliased_set_->max_expr_id())); |
| kill_.Add(new BitVector(aliased_set_->max_expr_id())); |
| in_.Add(new BitVector(aliased_set_->max_expr_id())); |
| |
| exposed_values_.Add(NULL); |
| out_values_.Add(NULL); |
| } |
| } |
| |
| bool Optimize() { |
| ComputeInitialSets(); |
| ComputeOutValues(); |
| ForwardLoads(); |
| EmitPhis(); |
| return forwarded_; |
| } |
| |
| private: |
| // Compute sets of loads generated and killed by each block. |
| // Additionally compute upwards exposed and generated loads for each block. |
| // Exposed loads are those that can be replaced if a corresponding |
| // reaching load will be found. |
| // Loads that are locally redundant will be replaced as we go through |
| // instructions. |
| void ComputeInitialSets() { |
| for (BlockIterator block_it = graph_->reverse_postorder_iterator(); |
| !block_it.Done(); |
| block_it.Advance()) { |
| BlockEntryInstr* block = block_it.Current(); |
| const intptr_t preorder_number = block->preorder_number(); |
| |
| BitVector* kill = kill_[preorder_number]; |
| BitVector* gen = gen_[preorder_number]; |
| |
| ZoneGrowableArray<Definition*>* exposed_values = NULL; |
| ZoneGrowableArray<Definition*>* out_values = NULL; |
| |
| for (ForwardInstructionIterator instr_it(block); |
| !instr_it.Done(); |
| instr_it.Advance()) { |
| Instruction* instr = instr_it.Current(); |
| |
| const Alias alias = aliased_set_->ComputeAliasForStore(instr); |
| if (!alias.IsNone()) { |
| // Interfering stores kill only loads from the same offset. |
| if (aliased_set_->Contains(alias)) { |
| BitVector* killed = aliased_set_->Get(alias); |
| kill->AddAll(killed); |
| // There is no need to clear out_values when clearing GEN set |
| // because only those values that are in the GEN set |
| // will ever be used. |
| gen->RemoveAll(killed); |
| |
| // Only forward stores to normal arrays and float64 arrays |
| // to loads because other array stores (intXX/uintXX/float32) |
| // may implicitly convert the value stored. |
| StoreIndexedInstr* array_store = instr->AsStoreIndexed(); |
| if (array_store == NULL || |
| array_store->class_id() == kArrayCid || |
| array_store->class_id() == kTypedDataFloat64ArrayCid) { |
| Definition* load = map_->Lookup(instr); |
| if (load != NULL) { |
| // Store has a corresponding numbered load. Try forwarding |
| // stored value to it. |
| gen->Add(load->expr_id()); |
| if (out_values == NULL) out_values = CreateBlockOutValues(); |
| (*out_values)[load->expr_id()] = GetStoredValue(instr); |
| } |
| } |
| } |
| ASSERT(!instr->IsDefinition() || |
| !IsLoadEliminationCandidate(instr->AsDefinition())); |
| continue; |
| } |
| |
| // Other instructions with side effects kill all loads. |
| if (!instr->Effects().IsNone()) { |
| kill->SetAll(); |
| // There is no need to clear out_values when clearing GEN set |
| // because only those values that are in the GEN set |
| // will ever be used. |
| gen->Clear(); |
| continue; |
| } |
| |
| Definition* defn = instr->AsDefinition(); |
| if ((defn == NULL) || !IsLoadEliminationCandidate(defn)) { |
| continue; |
| } |
| |
| const intptr_t expr_id = defn->expr_id(); |
| if (gen->Contains(expr_id)) { |
| // This is a locally redundant load. |
| ASSERT((out_values != NULL) && ((*out_values)[expr_id] != NULL)); |
| |
| Definition* replacement = (*out_values)[expr_id]; |
| EnsureSSATempIndex(graph_, defn, replacement); |
| if (FLAG_trace_optimization) { |
| OS::Print("Replacing load v%"Pd" with v%"Pd"\n", |
| defn->ssa_temp_index(), |
| replacement->ssa_temp_index()); |
| } |
| |
| defn->ReplaceUsesWith(replacement); |
| instr_it.RemoveCurrentFromGraph(); |
| forwarded_ = true; |
| continue; |
| } else if (!kill->Contains(expr_id)) { |
| // This is an exposed load: it is the first representative of a |
| // given expression id and it is not killed on the path from |
| // the block entry. |
| if (exposed_values == NULL) { |
| static const intptr_t kMaxExposedValuesInitialSize = 5; |
| exposed_values = new ZoneGrowableArray<Definition*>( |
| Utils::Minimum(kMaxExposedValuesInitialSize, |
| aliased_set_->max_expr_id())); |
| } |
| |
| exposed_values->Add(defn); |
| } |
| |
| gen->Add(expr_id); |
| |
| if (out_values == NULL) out_values = CreateBlockOutValues(); |
| (*out_values)[expr_id] = defn; |
| } |
| |
| out_[preorder_number]->CopyFrom(gen); |
| exposed_values_[preorder_number] = exposed_values; |
| out_values_[preorder_number] = out_values; |
| } |
| } |
| |
| // Compute OUT sets and corresponding out_values mappings by propagating them |
| // iteratively until fix point is reached. |
| // No replacement is done at this point and thus any out_value[expr_id] is |
| // changed at most once: from NULL to an actual value. |
| // When merging incoming loads we might need to create a phi. |
| // These phis are not inserted at the graph immediately because some of them |
| // might become redundant after load forwarding is done. |
| void ComputeOutValues() { |
| BitVector* temp = new BitVector(aliased_set_->max_expr_id()); |
| |
| bool changed = true; |
| while (changed) { |
| changed = false; |
| |
| for (BlockIterator block_it = graph_->reverse_postorder_iterator(); |
| !block_it.Done(); |
| block_it.Advance()) { |
| BlockEntryInstr* block = block_it.Current(); |
| |
| const intptr_t preorder_number = block->preorder_number(); |
| |
| BitVector* block_in = in_[preorder_number]; |
| BitVector* block_out = out_[preorder_number]; |
| BitVector* block_kill = kill_[preorder_number]; |
| BitVector* block_gen = gen_[preorder_number]; |
| |
| if (FLAG_trace_optimization) { |
| OS::Print("B%"Pd"", block->block_id()); |
| block_in->Print(); |
| block_out->Print(); |
| block_kill->Print(); |
| block_gen->Print(); |
| OS::Print("\n"); |
| } |
| |
| ZoneGrowableArray<Definition*>* block_out_values = |
| out_values_[preorder_number]; |
| |
| // Compute block_in as the intersection of all out(p) where p |
| // is a predecessor of the current block. |
| if (block->IsGraphEntry()) { |
| temp->Clear(); |
| } else { |
| // TODO(vegorov): this can be optimized for the case of a single |
| // predecessor. |
| // TODO(vegorov): this can be reordered to reduce amount of operations |
| // temp->CopyFrom(first_predecessor) |
| temp->SetAll(); |
| ASSERT(block->PredecessorCount() > 0); |
| for (intptr_t i = 0; i < block->PredecessorCount(); i++) { |
| BlockEntryInstr* pred = block->PredecessorAt(i); |
| BitVector* pred_out = out_[pred->preorder_number()]; |
| temp->Intersect(pred_out); |
| } |
| } |
| |
| if (!temp->Equals(*block_in)) { |
| // If IN set has changed propagate the change to OUT set. |
| block_in->CopyFrom(temp); |
| if (block_out->KillAndAdd(block_kill, block_in)) { |
| // If OUT set has changed then we have new values available out of |
| // the block. Compute these values creating phi where necessary. |
| for (BitVector::Iterator it(block_out); |
| !it.Done(); |
| it.Advance()) { |
| const intptr_t expr_id = it.Current(); |
| |
| if (block_out_values == NULL) { |
| out_values_[preorder_number] = block_out_values = |
| CreateBlockOutValues(); |
| } |
| |
| if ((*block_out_values)[expr_id] == NULL) { |
| ASSERT(block->PredecessorCount() > 0); |
| (*block_out_values)[expr_id] = |
| MergeIncomingValues(block, expr_id); |
| } |
| } |
| changed = true; |
| } |
| } |
| |
| if (FLAG_trace_optimization) { |
| OS::Print("after B%"Pd"", block->block_id()); |
| block_in->Print(); |
| block_out->Print(); |
| block_kill->Print(); |
| block_gen->Print(); |
| OS::Print("\n"); |
| } |
| } |
| } |
| } |
| |
| // Compute incoming value for the given expression id. |
| // Will create a phi if different values are incoming from multiple |
| // predecessors. |
| Definition* MergeIncomingValues(BlockEntryInstr* block, intptr_t expr_id) { |
| // First check if the same value is coming in from all predecessors. |
| Definition* incoming = NULL; |
| for (intptr_t i = 0; i < block->PredecessorCount(); i++) { |
| BlockEntryInstr* pred = block->PredecessorAt(i); |
| ZoneGrowableArray<Definition*>* pred_out_values = |
| out_values_[pred->preorder_number()]; |
| if (incoming == NULL) { |
| incoming = (*pred_out_values)[expr_id]; |
| } else if (incoming != (*pred_out_values)[expr_id]) { |
| incoming = NULL; |
| break; |
| } |
| } |
| |
| if (incoming != NULL) { |
| return incoming; |
| } |
| |
| // Incoming values are different. Phi is required to merge. |
| PhiInstr* phi = new PhiInstr( |
| block->AsJoinEntry(), block->PredecessorCount()); |
| |
| for (intptr_t i = 0; i < block->PredecessorCount(); i++) { |
| BlockEntryInstr* pred = block->PredecessorAt(i); |
| ZoneGrowableArray<Definition*>* pred_out_values = |
| out_values_[pred->preorder_number()]; |
| ASSERT((*pred_out_values)[expr_id] != NULL); |
| |
| // Sets of outgoing values are not linked into use lists so |
| // they might contain values that were replaced and removed |
| // from the graph by this iteration. |
| // To prevent using them we additionally mark definitions themselves |
| // as replaced and store a pointer to the replacement. |
| Definition* replacement = (*pred_out_values)[expr_id]->Replacement(); |
| Value* input = new Value(replacement); |
| phi->SetInputAt(i, input); |
| replacement->AddInputUse(input); |
| } |
| |
| phi->set_ssa_temp_index(graph_->alloc_ssa_temp_index()); |
| phis_.Add(phi); // Postpone phi insertion until after load forwarding. |
| |
| return phi; |
| } |
| |
| // Iterate over basic blocks and replace exposed loads with incoming |
| // values. |
| void ForwardLoads() { |
| for (BlockIterator block_it = graph_->reverse_postorder_iterator(); |
| !block_it.Done(); |
| block_it.Advance()) { |
| BlockEntryInstr* block = block_it.Current(); |
| |
| ZoneGrowableArray<Definition*>* loads = |
| exposed_values_[block->preorder_number()]; |
| if (loads == NULL) continue; // No exposed loads. |
| |
| BitVector* in = in_[block->preorder_number()]; |
| |
| for (intptr_t i = 0; i < loads->length(); i++) { |
| Definition* load = (*loads)[i]; |
| if (!in->Contains(load->expr_id())) continue; // No incoming value. |
| |
| Definition* replacement = MergeIncomingValues(block, load->expr_id()); |
| |
| // Sets of outgoing values are not linked into use lists so |
| // they might contain values that were replace and removed |
| // from the graph by this iteration. |
| // To prevent using them we additionally mark definitions themselves |
| // as replaced and store a pointer to the replacement. |
| replacement = replacement->Replacement(); |
| |
| if (load != replacement) { |
| EnsureSSATempIndex(graph_, load, replacement); |
| |
| if (FLAG_trace_optimization) { |
| OS::Print("Replacing load v%"Pd" with v%"Pd"\n", |
| load->ssa_temp_index(), |
| replacement->ssa_temp_index()); |
| } |
| |
| load->ReplaceUsesWith(replacement); |
| load->RemoveFromGraph(); |
| load->SetReplacement(replacement); |
| forwarded_ = true; |
| } |
| } |
| } |
| } |
| |
| // Check if the given phi take the same value on all code paths. |
| // Eliminate it as redundant if this is the case. |
| // When analyzing phi operands assumes that only generated during |
| // this load phase can be redundant. They can be distinguished because |
| // they are not marked alive. |
| // TODO(vegorov): move this into a separate phase over all phis. |
| bool EliminateRedundantPhi(PhiInstr* phi) { |
| Definition* value = NULL; // Possible value of this phi. |
| |
| worklist_.Clear(); |
| if (in_worklist_ == NULL) { |
| in_worklist_ = new BitVector(graph_->current_ssa_temp_index()); |
| } else { |
| in_worklist_->Clear(); |
| } |
| |
| worklist_.Add(phi); |
| in_worklist_->Add(phi->ssa_temp_index()); |
| |
| for (intptr_t i = 0; i < worklist_.length(); i++) { |
| PhiInstr* phi = worklist_[i]; |
| |
| for (intptr_t i = 0; i < phi->InputCount(); i++) { |
| Definition* input = phi->InputAt(i)->definition(); |
| if (input == phi) continue; |
| |
| PhiInstr* phi_input = input->AsPhi(); |
| if ((phi_input != NULL) && !phi_input->is_alive()) { |
| if (!in_worklist_->Contains(phi_input->ssa_temp_index())) { |
| worklist_.Add(phi_input); |
| in_worklist_->Add(phi_input->ssa_temp_index()); |
| } |
| continue; |
| } |
| |
| if (value == NULL) { |
| value = input; |
| } else if (value != input) { |
| return false; // This phi is not redundant. |
| } |
| } |
| } |
| |
| // All phis in the worklist are redundant and have the same computed |
| // value on all code paths. |
| ASSERT(value != NULL); |
| for (intptr_t i = 0; i < worklist_.length(); i++) { |
| worklist_[i]->ReplaceUsesWith(value); |
| } |
| |
| return true; |
| } |
| |
| // Phis have not yet been inserted into the graph but they have uses of |
| // their inputs. Insert the non-redundant ones and clear the input uses |
| // of the redundant ones. |
| void EmitPhis() { |
| for (intptr_t i = 0; i < phis_.length(); i++) { |
| PhiInstr* phi = phis_[i]; |
| if (phi->HasUses() && !EliminateRedundantPhi(phi)) { |
| phi->mark_alive(); |
| phi->block()->InsertPhi(phi); |
| } else { |
| for (intptr_t j = phi->InputCount() - 1; j >= 0; --j) { |
| phi->InputAt(j)->RemoveFromUseList(); |
| } |
| } |
| } |
| } |
| |
| ZoneGrowableArray<Definition*>* CreateBlockOutValues() { |
| ZoneGrowableArray<Definition*>* out = |
| new ZoneGrowableArray<Definition*>(aliased_set_->max_expr_id()); |
| for (intptr_t i = 0; i < aliased_set_->max_expr_id(); i++) { |
| out->Add(NULL); |
| } |
| return out; |
| } |
| |
| FlowGraph* graph_; |
| DirectChainedHashMap<LoadKeyValueTrait>* map_; |
| |
| // Mapping between field offsets in words and expression ids of loads from |
| // that offset. |
| AliasedSet* aliased_set_; |
| |
| // Per block sets of expression ids for loads that are: incoming (available |
| // on the entry), outgoing (available on the exit), generated and killed. |
| GrowableArray<BitVector*> in_; |
| GrowableArray<BitVector*> out_; |
| GrowableArray<BitVector*> gen_; |
| GrowableArray<BitVector*> kill_; |
| |
| // Per block list of upwards exposed loads. |
| GrowableArray<ZoneGrowableArray<Definition*>*> exposed_values_; |
| |
| // Per block mappings between expression ids and outgoing definitions that |
| // represent those ids. |
| GrowableArray<ZoneGrowableArray<Definition*>*> out_values_; |
| |
| // List of phis generated during ComputeOutValues and ForwardLoads. |
| // Some of these phis might be redundant and thus a separate pass is |
| // needed to emit only non-redundant ones. |
| GrowableArray<PhiInstr*> phis_; |
| |
| // Auxiliary worklist used by redundant phi elimination. |
| GrowableArray<PhiInstr*> worklist_; |
| BitVector* in_worklist_; |
| |
| // True if any load was eliminated. |
| bool forwarded_; |
| |
| DISALLOW_COPY_AND_ASSIGN(LoadOptimizer); |
| }; |
| |
| |
| class CSEInstructionMap : public ValueObject { |
| public: |
| // Right now CSE and LICM track a single effect: possible externalization of |
| // strings. |
| // Other effects like modifications of fields are tracked in a separate load |
| // forwarding pass via Alias structure. |
| COMPILE_ASSERT(EffectSet::kLastEffect == 1, single_effect_is_tracked); |
| |
| CSEInstructionMap() : independent_(), dependent_() { } |
| explicit CSEInstructionMap(const CSEInstructionMap& other) |
| : ValueObject(), |
| independent_(other.independent_), |
| dependent_(other.dependent_) { |
| } |
| |
| void RemoveAffected(EffectSet effects) { |
| if (!effects.IsNone()) { |
| dependent_.Clear(); |
| } |
| } |
| |
| Instruction* Lookup(Instruction* other) const { |
| return GetMapFor(other)->Lookup(other); |
| } |
| |
| void Insert(Instruction* instr) { |
| return GetMapFor(instr)->Insert(instr); |
| } |
| |
| private: |
| typedef DirectChainedHashMap<PointerKeyValueTrait<Instruction> > Map; |
| |
| Map* GetMapFor(Instruction* instr) { |
| return instr->Dependencies().IsNone() ? &independent_ : &dependent_; |
| } |
| |
| const Map* GetMapFor(Instruction* instr) const { |
| return instr->Dependencies().IsNone() ? &independent_ : &dependent_; |
| } |
| |
| // All computations that are not affected by any side-effect. |
| // Majority of computations are not affected by anything and will be in |
| // this map. |
| Map independent_; |
| |
| // All computations that are affected by side effect. |
| Map dependent_; |
| }; |
| |
| |
| bool DominatorBasedCSE::Optimize(FlowGraph* graph) { |
| bool changed = false; |
| if (FLAG_load_cse) { |
| GrowableArray<BitVector*> kill_by_offs(10); |
| DirectChainedHashMap<LoadKeyValueTrait> map; |
| AliasedSet* aliased_set = NumberLoadExpressions(graph, &map); |
| if (!aliased_set->IsEmpty()) { |
| // If any loads were forwarded return true from Optimize to run load |
| // forwarding again. This will allow to forward chains of loads. |
| // This is especially important for context variables as they are built |
| // as loads from loaded context. |
| // TODO(vegorov): renumber newly discovered congruences during the |
| // forwarding to forward chains without running whole pass twice. |
| LoadOptimizer load_optimizer(graph, aliased_set, &map); |
| changed = load_optimizer.Optimize() || changed; |
| } |
| } |
| |
| CSEInstructionMap map; |
| changed = OptimizeRecursive(graph, graph->graph_entry(), &map) || changed; |
| |
| return changed; |
| } |
| |
| |
| bool DominatorBasedCSE::OptimizeRecursive( |
| FlowGraph* graph, |
| BlockEntryInstr* block, |
| CSEInstructionMap* map) { |
| bool changed = false; |
| for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
| Instruction* current = it.Current(); |
| if (current->AllowsCSE()) { |
| Instruction* replacement = map->Lookup(current); |
| if ((replacement != NULL) && |
| graph->block_effects()->IsAvailableAt(replacement, block)) { |
| // Replace current with lookup result. |
| ReplaceCurrentInstruction(&it, current, replacement, graph); |
| changed = true; |
| continue; |
| } |
| |
| // For simplicity we assume that instruction either does not depend on |
| // anything or does not affect anything. If this is not the case then |
| // we should first remove affected instructions from the map and |
| // then add instruction to the map so that it does not kill itself. |
| ASSERT(current->Effects().IsNone() || current->Dependencies().IsNone()); |
| map->Insert(current); |
| } |
| |
| map->RemoveAffected(current->Effects()); |
| } |
| |
| // Process children in the dominator tree recursively. |
| intptr_t num_children = block->dominated_blocks().length(); |
| for (intptr_t i = 0; i < num_children; ++i) { |
| BlockEntryInstr* child = block->dominated_blocks()[i]; |
| if (i < num_children - 1) { |
| // Copy map. |
| CSEInstructionMap child_map(*map); |
| changed = OptimizeRecursive(graph, child, &child_map) || changed; |
| } else { |
| // Reuse map for the last child. |
| changed = OptimizeRecursive(graph, child, map) || changed; |
| } |
| } |
| return changed; |
| } |
| |
| |
| ConstantPropagator::ConstantPropagator( |
| FlowGraph* graph, |
| const GrowableArray<BlockEntryInstr*>& ignored) |
| : FlowGraphVisitor(ignored), |
| graph_(graph), |
| unknown_(Object::transition_sentinel()), |
| non_constant_(Object::sentinel()), |
| reachable_(new BitVector(graph->preorder().length())), |
| definition_marks_(new BitVector(graph->max_virtual_register_number())), |
| block_worklist_(), |
| definition_worklist_() {} |
| |
| |
| void ConstantPropagator::Optimize(FlowGraph* graph) { |
| GrowableArray<BlockEntryInstr*> ignored; |
| ConstantPropagator cp(graph, ignored); |
| cp.Analyze(); |
| cp.Transform(); |
| } |
| |
| |
| void ConstantPropagator::OptimizeBranches(FlowGraph* graph) { |
| GrowableArray<BlockEntryInstr*> ignored; |
| ConstantPropagator cp(graph, ignored); |
| cp.VisitBranches(); |
| cp.Transform(); |
| } |
| |
| |
| void ConstantPropagator::SetReachable(BlockEntryInstr* block) { |
| if (!reachable_->Contains(block->preorder_number())) { |
| reachable_->Add(block->preorder_number()); |
| block_worklist_.Add(block); |
| } |
| } |
| |
| |
| void ConstantPropagator::SetValue(Definition* definition, const Object& value) { |
| // We would like to assert we only go up (toward non-constant) in the lattice. |
| // |
| // ASSERT(IsUnknown(definition->constant_value()) || |
| // IsNonConstant(value) || |
| // (definition->constant_value().raw() == value.raw())); |
| // |
| // But the final disjunct is not true (e.g., mint or double constants are |
| // heap-allocated and so not necessarily pointer-equal on each iteration). |
| if (definition->constant_value().raw() != value.raw()) { |
| definition->constant_value() = value.raw(); |
| if (definition->input_use_list() != NULL) { |
| ASSERT(definition->HasSSATemp()); |
| if (!definition_marks_->Contains(definition->ssa_temp_index())) { |
| definition_worklist_.Add(definition); |
| definition_marks_->Add(definition->ssa_temp_index()); |
| } |
| } |
| } |
| } |
| |
| |
| // Compute the join of two values in the lattice, assign it to the first. |
| void ConstantPropagator::Join(Object* left, const Object& right) { |
| // Join(non-constant, X) = non-constant |
| // Join(X, unknown) = X |
| if (IsNonConstant(*left) || IsUnknown(right)) return; |
| |
| // Join(unknown, X) = X |
| // Join(X, non-constant) = non-constant |
| if (IsUnknown(*left) || IsNonConstant(right)) { |
| *left = right.raw(); |
| return; |
| } |
| |
| // Join(X, X) = X |
| // TODO(kmillikin): support equality for doubles, mints, etc. |
| if (left->raw() == right.raw()) return; |
| |
| // Join(X, Y) = non-constant |
| *left = non_constant_.raw(); |
| } |
| |
| |
| // -------------------------------------------------------------------------- |
| // 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()); |
| } |
| |
| |
| 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) { |
| 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(); |
| } |
| |
| |
| // -------------------------------------------------------------------------- |
| // Analysis of control instructions. Unconditional successors are |
| // reachable. Conditional successors are reachable depending on the |
| // constant value of the condition. |
| void ConstantPropagator::VisitReturn(ReturnInstr* instr) { |
| // Nothing to do. |
| } |
| |
| |
| void ConstantPropagator::VisitThrow(ThrowInstr* instr) { |
| // Nothing to do. |
| } |
| |
| |
| void ConstantPropagator::VisitReThrow(ReThrowInstr* instr) { |
| // Nothing to do. |
| } |
| |
| |
| void ConstantPropagator::VisitGoto(GotoInstr* instr) { |
| SetReachable(instr->successor()); |
| |
| // Phi value depends on the reachability of a predecessor. We have |
| // to revisit phis every time a predecessor becomes reachable. |
| for (PhiIterator it(instr->successor()); !it.Done(); it.Advance()) { |
| it.Current()->Accept(this); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitBranch(BranchInstr* instr) { |
| instr->comparison()->Accept(this); |
| |
| // The successors may be reachable, but only if this instruction is. (We |
| // might be analyzing it because the constant value of one of its inputs |
| // has changed.) |
| if (reachable_->Contains(instr->GetBlock()->preorder_number())) { |
| const Object& value = instr->comparison()->constant_value(); |
| if (IsNonConstant(value)) { |
| SetReachable(instr->true_successor()); |
| SetReachable(instr->false_successor()); |
| } else if (value.raw() == Bool::True().raw()) { |
| SetReachable(instr->true_successor()); |
| } else if (!IsUnknown(value)) { // Any other constant. |
| SetReachable(instr->false_successor()); |
| } |
| } |
| } |
| |
| |
| // -------------------------------------------------------------------------- |
| // Analysis of non-definition instructions. They do not have values so they |
| // cannot have constant values. |
| void ConstantPropagator::VisitStoreContext(StoreContextInstr* instr) { } |
| |
| |
| void ConstantPropagator::VisitChainContext(ChainContextInstr* instr) { } |
| |
| |
| void ConstantPropagator::VisitCatchEntry(CatchEntryInstr* instr) { } |
| |
| |
| void ConstantPropagator::VisitCheckStackOverflow( |
| CheckStackOverflowInstr* instr) { } |
| |
| |
| void ConstantPropagator::VisitCheckClass(CheckClassInstr* instr) { } |
| |
| void ConstantPropagator::VisitGuardField(GuardFieldInstr* instr) { } |
| |
| void ConstantPropagator::VisitCheckSmi(CheckSmiInstr* instr) { } |
| |
| |
| void ConstantPropagator::VisitCheckEitherNonSmi( |
| CheckEitherNonSmiInstr* instr) { } |
| |
| |
| void ConstantPropagator::VisitCheckArrayBound(CheckArrayBoundInstr* instr) { } |
| |
| |
| // -------------------------------------------------------------------------- |
| // Analysis of definitions. Compute the constant value. If it has changed |
| // and the definition has input uses, add the definition to the definition |
| // worklist so that the used can be processed. |
| void ConstantPropagator::VisitPhi(PhiInstr* instr) { |
| // Compute the join over all the reachable predecessor values. |
| JoinEntryInstr* block = instr->block(); |
| Object& value = Object::ZoneHandle(Unknown()); |
| for (intptr_t pred_idx = 0; pred_idx < instr->InputCount(); ++pred_idx) { |
| if (reachable_->Contains( |
| block->PredecessorAt(pred_idx)->preorder_number())) { |
| Join(&value, |
| instr->InputAt(pred_idx)->definition()->constant_value()); |
| } |
| } |
| SetValue(instr, value); |
| } |
| |
| |
| void ConstantPropagator::VisitParameter(ParameterInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitPushArgument(PushArgumentInstr* instr) { |
| SetValue(instr, instr->value()->definition()->constant_value()); |
| } |
| |
| |
| void ConstantPropagator::VisitAssertAssignable(AssertAssignableInstr* instr) { |
| const Object& value = instr->value()->definition()->constant_value(); |
| if (IsNonConstant(value)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(value)) { |
| // We are ignoring the instantiator and instantiator_type_arguments, but |
| // still monotonic and safe. |
| // TODO(kmillikin): Handle constants. |
| SetValue(instr, non_constant_); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitAssertBoolean(AssertBooleanInstr* instr) { |
| const Object& value = instr->value()->definition()->constant_value(); |
| if (IsNonConstant(value)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(value)) { |
| // TODO(kmillikin): Handle assertion. |
| SetValue(instr, non_constant_); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitArgumentDefinitionTest( |
| ArgumentDefinitionTestInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitCurrentContext(CurrentContextInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitClosureCall(ClosureCallInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitInstanceCall(InstanceCallInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitPolymorphicInstanceCall( |
| PolymorphicInstanceCallInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitStaticCall(StaticCallInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitLoadLocal(LoadLocalInstr* instr) { |
| // Instruction is eliminated when translating to SSA. |
| UNREACHABLE(); |
| } |
| |
| |
| void ConstantPropagator::VisitStoreLocal(StoreLocalInstr* instr) { |
| // Instruction is eliminated when translating to SSA. |
| UNREACHABLE(); |
| } |
| |
| |
| void ConstantPropagator::VisitIfThenElse(IfThenElseInstr* instr) { |
| ASSERT(Token::IsEqualityOperator(instr->kind())); |
| |
| const Object& left = instr->left()->definition()->constant_value(); |
| const Object& right = instr->right()->definition()->constant_value(); |
| |
| if (IsNonConstant(left) || IsNonConstant(right)) { |
| // TODO(vegorov): incorporate nullability information into the lattice. |
| 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 || |
| instr->kind() == Token::kNE) { |
| result = !result; |
| } |
| SetValue(instr, Smi::Handle( |
| Smi::New(result ? instr->if_true() : instr->if_false()))); |
| } else { |
| SetValue(instr, non_constant_); |
| } |
| } else if (IsConstant(left) && IsConstant(right)) { |
| bool result = (left.raw() == right.raw()); |
| if (instr->kind() == Token::kNE_STRICT || |
| instr->kind() == Token::kNE) { |
| result = !result; |
| } |
| SetValue(instr, Smi::Handle( |
| Smi::New(result ? instr->if_true() : instr->if_false()))); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitStrictCompare(StrictCompareInstr* instr) { |
| const Object& left = instr->left()->definition()->constant_value(); |
| const Object& right = instr->right()->definition()->constant_value(); |
| |
| if (IsNonConstant(left) || IsNonConstant(right)) { |
| // TODO(vegorov): incorporate nullability information into the lattice. |
| 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 { |
| SetValue(instr, non_constant_); |
| } |
| } else if (IsConstant(left) && IsConstant(right)) { |
| bool result = (left.raw() == right.raw()); |
| if (instr->kind() == Token::kNE_STRICT) result = !result; |
| SetValue(instr, result ? Bool::True() : Bool::False()); |
| } |
| } |
| |
| |
| static bool CompareIntegers(Token::Kind kind, |
| const Integer& left, |
| const Integer& right) { |
| const int result = left.CompareWith(right); |
| switch (kind) { |
| case Token::kEQ: return (result == 0); |
| case Token::kNE: return (result != 0); |
| case Token::kLT: return (result < 0); |
| case Token::kGT: return (result > 0); |
| case Token::kLTE: return (result <= 0); |
| case Token::kGTE: return (result >= 0); |
| default: |
| UNREACHABLE(); |
| return false; |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitEqualityCompare(EqualityCompareInstr* instr) { |
| const Object& left = instr->left()->definition()->constant_value(); |
| const Object& right = instr->right()->definition()->constant_value(); |
| if (IsNonConstant(left) || IsNonConstant(right)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(left) && IsConstant(right)) { |
| if (left.IsInteger() && right.IsInteger()) { |
| const bool result = CompareIntegers(instr->kind(), |
| Integer::Cast(left), |
| Integer::Cast(right)); |
| SetValue(instr, result ? Bool::True() : Bool::False()); |
| } else { |
| SetValue(instr, non_constant_); |
| } |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitRelationalOp(RelationalOpInstr* instr) { |
| const Object& left = instr->left()->definition()->constant_value(); |
| const Object& right = instr->right()->definition()->constant_value(); |
| if (IsNonConstant(left) || IsNonConstant(right)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(left) && IsConstant(right)) { |
| if (left.IsInteger() && right.IsInteger()) { |
| const bool result = CompareIntegers(instr->kind(), |
| Integer::Cast(left), |
| Integer::Cast(right)); |
| SetValue(instr, result ? Bool::True() : Bool::False()); |
| } else { |
| SetValue(instr, non_constant_); |
| } |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitNativeCall(NativeCallInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitStringFromCharCode( |
| StringFromCharCodeInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitLoadIndexed(LoadIndexedInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitStoreIndexed(StoreIndexedInstr* instr) { |
| SetValue(instr, instr->value()->definition()->constant_value()); |
| } |
| |
| |
| void ConstantPropagator::VisitStoreInstanceField( |
| StoreInstanceFieldInstr* instr) { |
| SetValue(instr, instr->value()->definition()->constant_value()); |
| } |
| |
| |
| void ConstantPropagator::VisitLoadStaticField(LoadStaticFieldInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitStoreStaticField(StoreStaticFieldInstr* instr) { |
| SetValue(instr, instr->value()->definition()->constant_value()); |
| } |
| |
| |
| void ConstantPropagator::VisitBooleanNegate(BooleanNegateInstr* instr) { |
| const Object& value = instr->value()->definition()->constant_value(); |
| if (IsNonConstant(value)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(value)) { |
| bool val = value.raw() != Bool::True().raw(); |
| SetValue(instr, val ? Bool::True() : Bool::False()); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitInstanceOf(InstanceOfInstr* instr) { |
| const Object& value = instr->value()->definition()->constant_value(); |
| if (IsNonConstant(value)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(value)) { |
| // TODO(kmillikin): Handle instanceof on constants. |
| SetValue(instr, non_constant_); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitCreateArray(CreateArrayInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitCreateClosure(CreateClosureInstr* instr) { |
| // TODO(kmillikin): Treat closures as constants. |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitAllocateObject(AllocateObjectInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitAllocateObjectWithBoundsCheck( |
| AllocateObjectWithBoundsCheckInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitLoadUntagged(LoadUntaggedInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitLoadField(LoadFieldInstr* instr) { |
| if ((instr->recognized_kind() == MethodRecognizer::kObjectArrayLength) && |
| (instr->value()->definition()->IsCreateArray())) { |
| const intptr_t length = |
| instr->value()->definition()->AsCreateArray()->num_elements(); |
| const Object& result = Smi::ZoneHandle(Smi::New(length)); |
| SetValue(instr, result); |
| return; |
| } |
| |
| if (instr->IsImmutableLengthLoad()) { |
| ConstantInstr* constant = instr->value()->definition()->AsConstant(); |
| if (constant != NULL) { |
| if (constant->value().IsString()) { |
| SetValue(instr, Smi::ZoneHandle( |
| Smi::New(String::Cast(constant->value()).Length()))); |
| return; |
| } |
| if (constant->value().IsArray()) { |
| SetValue(instr, Smi::ZoneHandle( |
| Smi::New(Array::Cast(constant->value()).Length()))); |
| return; |
| } |
| } |
| } |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitStoreVMField(StoreVMFieldInstr* instr) { |
| SetValue(instr, instr->value()->definition()->constant_value()); |
| } |
| |
| |
| void ConstantPropagator::VisitInstantiateTypeArguments( |
| InstantiateTypeArgumentsInstr* instr) { |
| const Object& object = |
| instr->instantiator()->definition()->constant_value(); |
| if (IsNonConstant(object)) { |
| SetValue(instr, non_constant_); |
| return; |
| } |
| if (IsConstant(object)) { |
| const intptr_t len = instr->type_arguments().Length(); |
| if (instr->type_arguments().IsRawInstantiatedRaw(len) && |
| object.IsNull()) { |
| SetValue(instr, object); |
| return; |
| } |
| if (instr->type_arguments().IsUninstantiatedIdentity() || |
| instr->type_arguments().CanShareInstantiatorTypeArguments( |
| instr->instantiator_class())) { |
| SetValue(instr, object); |
| return; |
| } |
| SetValue(instr, non_constant_); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitExtractConstructorTypeArguments( |
| ExtractConstructorTypeArgumentsInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitExtractConstructorInstantiator( |
| ExtractConstructorInstantiatorInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitAllocateContext(AllocateContextInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitCloneContext(CloneContextInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitBinarySmiOp(BinarySmiOpInstr* instr) { |
| const Object& left = instr->left()->definition()->constant_value(); |
| const Object& right = instr->right()->definition()->constant_value(); |
| if (IsNonConstant(left) || IsNonConstant(right)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(left) && IsConstant(right)) { |
| if (left.IsSmi() && right.IsSmi()) { |
| const Smi& left_smi = Smi::Cast(left); |
| const Smi& right_smi = Smi::Cast(right); |
| switch (instr->op_kind()) { |
| case Token::kADD: |
| case Token::kSUB: |
| case Token::kMUL: |
| case Token::kTRUNCDIV: |
| case Token::kMOD: { |
| const Object& result = Integer::ZoneHandle( |
| left_smi.ArithmeticOp(instr->op_kind(), right_smi)); |
| SetValue(instr, result); |
| break; |
| } |
| case Token::kSHL: |
| case Token::kSHR: { |
| const Object& result = Integer::ZoneHandle( |
| left_smi.ShiftOp(instr->op_kind(), right_smi)); |
| SetValue(instr, result); |
| break; |
| } |
| case Token::kBIT_AND: |
| case Token::kBIT_OR: |
| case Token::kBIT_XOR: { |
| const Object& result = Integer::ZoneHandle( |
| left_smi.BitOp(instr->op_kind(), right_smi)); |
| SetValue(instr, result); |
| break; |
| } |
| default: |
| // TODO(kmillikin): support other smi operations. |
| SetValue(instr, non_constant_); |
| } |
| } else { |
| // TODO(kmillikin): support other types. |
| SetValue(instr, non_constant_); |
| } |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitBoxInteger(BoxIntegerInstr* instr) { |
| // TODO(kmillikin): Handle box operation. |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitUnboxInteger(UnboxIntegerInstr* instr) { |
| // TODO(kmillikin): Handle unbox operation. |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitBinaryMintOp( |
| BinaryMintOpInstr* instr) { |
| // TODO(kmillikin): Handle binary operations. |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitShiftMintOp( |
| ShiftMintOpInstr* instr) { |
| // TODO(kmillikin): Handle shift operations. |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitUnaryMintOp( |
| UnaryMintOpInstr* instr) { |
| // TODO(kmillikin): Handle unary operations. |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitUnarySmiOp(UnarySmiOpInstr* instr) { |
| const Object& value = instr->value()->definition()->constant_value(); |
| if (IsNonConstant(value)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(value)) { |
| // TODO(kmillikin): Handle unary operations. |
| SetValue(instr, non_constant_); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitSmiToDouble(SmiToDoubleInstr* instr) { |
| const Object& value = instr->value()->definition()->constant_value(); |
| if (IsConstant(value) && value.IsInteger()) { |
| SetValue(instr, Double::Handle( |
| Double::New(Integer::Cast(value).AsDoubleValue(), Heap::kOld))); |
| } else if (IsNonConstant(value)) { |
| SetValue(instr, non_constant_); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitDoubleToInteger(DoubleToIntegerInstr* instr) { |
| // TODO(kmillikin): Handle conversion. |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitDoubleToSmi(DoubleToSmiInstr* instr) { |
| // TODO(kmillikin): Handle conversion. |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitDoubleToDouble(DoubleToDoubleInstr* instr) { |
| // TODO(kmillikin): Handle conversion. |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitInvokeMathCFunction( |
| InvokeMathCFunctionInstr* instr) { |
| // TODO(kmillikin): Handle conversion. |
| SetValue(instr, non_constant_); |
| } |
| |
| void ConstantPropagator::VisitConstant(ConstantInstr* instr) { |
| SetValue(instr, instr->value()); |
| } |
| |
| |
| void ConstantPropagator::VisitConstraint(ConstraintInstr* instr) { |
| // Should not be used outside of range analysis. |
| UNREACHABLE(); |
| } |
| |
| |
| void ConstantPropagator::VisitBinaryDoubleOp( |
| BinaryDoubleOpInstr* instr) { |
| const Object& left = instr->left()->definition()->constant_value(); |
| const Object& right = instr->right()->definition()->constant_value(); |
| if (IsNonConstant(left) || IsNonConstant(right)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(left) && IsConstant(right)) { |
| // TODO(kmillikin): Handle binary operation. |
| SetValue(instr, non_constant_); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitBinaryFloat32x4Op( |
| BinaryFloat32x4OpInstr* instr) { |
| const Object& left = instr->left()->definition()->constant_value(); |
| const Object& right = instr->right()->definition()->constant_value(); |
| if (IsNonConstant(left) || IsNonConstant(right)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(left) && IsConstant(right)) { |
| // TODO(kmillikin): Handle binary operation. |
| SetValue(instr, non_constant_); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitFloat32x4Constructor( |
| Float32x4ConstructorInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitFloat32x4Shuffle(Float32x4ShuffleInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitFloat32x4Zero(Float32x4ZeroInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitFloat32x4Splat(Float32x4SplatInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitFloat32x4Comparison( |
| Float32x4ComparisonInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitFloat32x4MinMax(Float32x4MinMaxInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitFloat32x4Scale(Float32x4ScaleInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitFloat32x4Sqrt(Float32x4SqrtInstr* instr) { |
| SetValue(instr, non_constant_); |
| } |
| |
| |
| void ConstantPropagator::VisitMathSqrt(MathSqrtInstr* instr) { |
| const Object& value = instr->value()->definition()->constant_value(); |
| if (IsNonConstant(value)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(value)) { |
| // TODO(kmillikin): Handle sqrt. |
| SetValue(instr, non_constant_); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitUnboxDouble(UnboxDoubleInstr* instr) { |
| const Object& value = instr->value()->definition()->constant_value(); |
| if (IsNonConstant(value)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(value)) { |
| // TODO(kmillikin): Handle conversion. |
| SetValue(instr, non_constant_); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitBoxDouble(BoxDoubleInstr* instr) { |
| const Object& value = instr->value()->definition()->constant_value(); |
| if (IsNonConstant(value)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(value)) { |
| // TODO(kmillikin): Handle conversion. |
| SetValue(instr, non_constant_); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitUnboxFloat32x4(UnboxFloat32x4Instr* instr) { |
| const Object& value = instr->value()->definition()->constant_value(); |
| if (IsNonConstant(value)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(value)) { |
| // TODO(kmillikin): Handle conversion. |
| SetValue(instr, non_constant_); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitBoxFloat32x4(BoxFloat32x4Instr* instr) { |
| const Object& value = instr->value()->definition()->constant_value(); |
| if (IsNonConstant(value)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(value)) { |
| // TODO(kmillikin): Handle conversion. |
| SetValue(instr, non_constant_); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitUnboxUint32x4(UnboxUint32x4Instr* instr) { |
| const Object& value = instr->value()->definition()->constant_value(); |
| if (IsNonConstant(value)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(value)) { |
| // TODO(kmillikin): Handle conversion. |
| SetValue(instr, non_constant_); |
| } |
| } |
| |
| |
| void ConstantPropagator::VisitBoxUint32x4(BoxUint32x4Instr* instr) { |
| const Object& value = instr->value()->definition()->constant_value(); |
| if (IsNonConstant(value)) { |
| SetValue(instr, non_constant_); |
| } else if (IsConstant(value)) { |
| // TODO(kmillikin): Handle conversion. |
| SetValue(instr, non_constant_); |
| } |
| } |
| |
| |
| void ConstantPropagator::Analyze() { |
| GraphEntryInstr* entry = graph_->graph_entry(); |
| reachable_->Add(entry->preorder_number()); |
| block_worklist_.Add(entry); |
| |
| while (true) { |
| if (block_worklist_.is_empty()) { |
| if (definition_worklist_.is_empty()) break; |
| Definition* definition = definition_worklist_.RemoveLast(); |
| definition_marks_->Remove(definition->ssa_temp_index()); |
| Value* use = definition->input_use_list(); |
| while (use != NULL) { |
| use->instruction()->Accept(this); |
| use = use->next_use(); |
| } |
| } else { |
| 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()); |
| |
| while (!block_worklist_.is_empty()) { |
| BlockEntryInstr* block = block_worklist_.RemoveLast(); |
| 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()) { |
| SetReachable(branch->true_successor()); |
| } else { |
| ASSERT(branch->constant_target() == branch->false_successor()); |
| SetReachable(branch->false_successor()); |
| } |
| } else { |
| // No new information: Assume both targets are reachable. |
| SetReachable(branch->true_successor()); |
| SetReachable(branch->false_successor()); |
| } |
| } |
| } |
| } |
| |
| |
| void ConstantPropagator::Transform() { |
| if (FLAG_trace_constant_propagation) { |
| OS::Print("\n==== Before constant propagation ====\n"); |
| FlowGraphPrinter printer(*graph_); |
| printer.PrintBlocks(); |
| } |
| |
| GrowableArray<PhiInstr*> redundant_phis(10); |
| |
| // We will recompute dominators, block ordering, block ids, block last |
| // instructions, previous pointers, predecessors, etc. after eliminating |
| // unreachable code. We do not maintain those properties during the |
| // transformation. |
| for (BlockIterator b = graph_->reverse_postorder_iterator(); |
| !b.Done(); |
| b.Advance()) { |
| BlockEntryInstr* block = b.Current(); |
| JoinEntryInstr* join = block->AsJoinEntry(); |
| if (!reachable_->Contains(block->preorder_number())) { |
| if (FLAG_trace_constant_propagation) { |
| OS::Print("Unreachable B%"Pd"\n", block->block_id()); |
| } |
| // Remove all uses in unreachable blocks. |
| if (join != NULL) { |
| for (PhiIterator it(join); !it.Done(); it.Advance()) { |
| it.Current()->UnuseAllInputs(); |
| } |
| } |
| block->UnuseAllInputs(); |
| for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
| it.Current()->UnuseAllInputs(); |
| } |
| continue; |
| } |
| |
| if (join != NULL) { |
| // Remove phi inputs corresponding to unreachable predecessor blocks. |
| // Predecessors will be recomputed (in block id order) after removing |
| // unreachable code so we merely have to keep the phi inputs in order. |
| ZoneGrowableArray<PhiInstr*>* phis = join->phis(); |
| if ((phis != NULL) && !phis->is_empty()) { |
| intptr_t pred_count = join->PredecessorCount(); |
| intptr_t live_count = 0; |
| for (intptr_t pred_idx = 0; pred_idx < pred_count; ++pred_idx) { |
| if (reachable_->Contains( |
| join->PredecessorAt(pred_idx)->preorder_number())) { |
| if (live_count < pred_idx) { |
| for (PhiIterator it(join); !it.Done(); it.Advance()) { |
| PhiInstr* phi = it.Current(); |
| ASSERT(phi != NULL); |
| phi->SetInputAt(live_count, phi->InputAt(pred_idx)); |
| } |
| } |
| ++live_count; |
| } else { |
| for (PhiIterator it(join); !it.Done(); it.Advance()) { |
| PhiInstr* phi = it.Current(); |
| ASSERT(phi != NULL); |
| phi->InputAt(pred_idx)->RemoveFromUseList(); |
| } |
| } |
| } |
| if (live_count < pred_count) { |
| intptr_t to_idx = 0; |
| for (intptr_t from_idx = 0; from_idx < phis->length(); ++from_idx) { |
| PhiInstr* phi = (*phis)[from_idx]; |
| ASSERT(phi != NULL); |
| if (FLAG_remove_redundant_phis && (live_count == 1)) { |
| Value* input = phi->InputAt(0); |
| phi->ReplaceUsesWith(input->definition()); |
| input->RemoveFromUseList(); |
| } else { |
| phi->inputs_.TruncateTo(live_count); |
| (*phis)[to_idx++] = phi; |
| } |
| } |
| if (to_idx == 0) { |
| join->phis_ = NULL; |
| } else { |
| phis->TruncateTo(to_idx); |
| } |
| } |
| } |
| } |
| |
| for (ForwardInstructionIterator i(block); !i.Done(); i.Advance()) { |
| Definition* defn = i.Current()->AsDefinition(); |
| // Replace constant-valued instructions without observable side |
| // effects. Do this for smis only to avoid having to copy other |
| // objects into the heap's old generation. |
| if ((defn != NULL) && |
| IsConstant(defn->constant_value()) && |
| (defn->constant_value().IsSmi() || defn->constant_value().IsOld()) && |
| !defn->IsConstant() && |
| !defn->IsPushArgument() && |
| !defn->IsStoreIndexed() && |
| !defn->IsStoreInstanceField() && |
| !defn->IsStoreStaticField() && |
| !defn->IsStoreVMField()) { |
| if (FLAG_trace_constant_propagation) { |
| OS::Print("Constant v%"Pd" = %s\n", |
| defn->ssa_temp_index(), |
| defn->constant_value().ToCString()); |
| } |
| defn->ReplaceWith(new ConstantInstr(defn->constant_value()), &i); |
| } |
| } |
| |
| // Replace branches where one target is unreachable with jumps. |
| BranchInstr* branch = block->last_instruction()->AsBranch(); |
| if (branch != NULL) { |
| TargetEntryInstr* if_true = branch->true_successor(); |
| TargetEntryInstr* if_false = branch->false_successor(); |
| JoinEntryInstr* join = NULL; |
| Instruction* next = NULL; |
| |
| if (!reachable_->Contains(if_true->preorder_number())) { |
| ASSERT(reachable_->Contains(if_false->preorder_number())); |
| ASSERT(if_false->parallel_move() == NULL); |
| ASSERT(if_false->loop_info() == NULL); |
| join = new JoinEntryInstr(if_false->block_id(), if_false->try_index()); |
| join->InheritDeoptTarget(if_false); |
| if_false->UnuseAllInputs(); |
| next = if_false->next(); |
| } else if (!reachable_->Contains(if_false->preorder_number())) { |
| ASSERT(if_true->parallel_move() == NULL); |
| ASSERT(if_true->loop_info() == NULL); |
| join = new JoinEntryInstr(if_true->block_id(), if_true->try_index()); |
| join->InheritDeoptTarget(if_true); |
| if_true->UnuseAllInputs(); |
| next = if_true->next(); |
| } |
| |
| if (join != NULL) { |
| // Replace the branch with a jump to the reachable successor. |
| // Drop the comparison, which does not have side effects as long |
| // as it is a strict compare (the only one we can determine is |
| // constant with the current analysis). |
| GotoInstr* jump = new GotoInstr(join); |
| jump->InheritDeoptTarget(branch); |
| |
| Instruction* previous = branch->previous(); |
| branch->set_previous(NULL); |
| previous->LinkTo(jump); |
| |
| // Replace the false target entry with the new join entry. We will |
| // recompute the dominators after this pass. |
| join->LinkTo(next); |
| branch->UnuseAllInputs(); |
| } |
| } |
| } |
| |
| graph_->DiscoverBlocks(); |
| GrowableArray<BitVector*> dominance_frontier; |
| graph_->ComputeDominators(&dominance_frontier); |
| |
| if (FLAG_trace_constant_propagation) { |
| OS::Print("\n==== After constant propagation ====\n"); |
| FlowGraphPrinter printer(*graph_); |
| printer.PrintBlocks(); |
| } |
| } |
| |
| |
| // Returns true if the given phi has a single input use and |
| // is used in the environments either at the corresponding block entry or |
| // at the same instruction where input use is. |
| static bool PhiHasSingleUse(PhiInstr* phi, Value* use) { |
| if ((use->next_use() != NULL) || (phi->input_use_list() != use)) { |
| return false; |
| } |
| |
| BlockEntryInstr* block = phi->block(); |
| for (Value* env_use = phi->env_use_list(); |
| env_use != NULL; |
| env_use = env_use->next_use()) { |
| if ((env_use->instruction() != block) && |
| (env_use->instruction() != use->instruction())) { |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| |
| bool BranchSimplifier::Match(JoinEntryInstr* block) { |
| // Match the pattern of a branch on a comparison whose left operand is a |
| // phi from the same block, and whose right operand is a constant. |
| // |
| // Branch(Comparison(kind, Phi, Constant)) |
| // |
| // These are the branches produced by inlining in a test context. Also, |
| // the phi and the constant have no other uses so they can simply be |
| // eliminated. The block has no other phis and no instructions |
| // intervening between the phi, constant, and branch so the block can |
| // simply be eliminated. |
| BranchInstr* branch = block->last_instruction()->AsBranch(); |
| ASSERT(branch != NULL); |
| ComparisonInstr* comparison = branch->comparison(); |
| Value* left = comparison->left(); |
| PhiInstr* phi = left->definition()->AsPhi(); |
| Value* right = comparison->right(); |
| ConstantInstr* constant = right->definition()->AsConstant(); |
| return (phi != NULL) && |
| (constant != NULL) && |
| (phi->GetBlock() == block) && |
| PhiHasSingleUse(phi, left) && |
| constant->HasOnlyUse(right) && |
| (block->next() == constant) && |
| (constant->next() == branch) && |
| (block->phis()->length() == 1); |
| } |
| |
| |
| JoinEntryInstr* BranchSimplifier::ToJoinEntry(TargetEntryInstr* target) { |
| // Convert a target block into a join block. Branches will be duplicated |
| // so the former true and false targets become joins of the control flows |
| // from all the duplicated branches. |
| JoinEntryInstr* join = |
| new JoinEntryInstr(target->block_id(), target->try_index()); |
| join->InheritDeoptTarget(target); |
| join->LinkTo(target->next()); |
| join->set_last_instruction(target->last_instruction()); |
| target->UnuseAllInputs(); |
| return join; |
| } |
| |
| |
| ConstantInstr* BranchSimplifier::CloneConstant(FlowGraph* flow_graph, |
| ConstantInstr* constant) { |
| ConstantInstr* new_constant = new ConstantInstr(constant->value()); |
| new_constant->set_ssa_temp_index(flow_graph->alloc_ssa_temp_index()); |
| return new_constant; |
| } |
| |
| |
| BranchInstr* BranchSimplifier::CloneBranch(BranchInstr* branch, |
| Value* left, |
| Value* right) { |
| ComparisonInstr* comparison = branch->comparison(); |
| ComparisonInstr* new_comparison = NULL; |
| if (comparison->IsStrictCompare()) { |
| new_comparison = new StrictCompareInstr(comparison->kind(), left, right); |
| } else if (comparison->IsEqualityCompare()) { |
| EqualityCompareInstr* equality_compare = comparison->AsEqualityCompare(); |
| EqualityCompareInstr* new_equality_compare = |
| new EqualityCompareInstr(equality_compare->token_pos(), |
| comparison->kind(), |
| left, |
| right); |
| new_equality_compare->set_ic_data(equality_compare->ic_data()); |
| new_comparison = new_equality_compare; |
| } else { |
| ASSERT(comparison->IsRelationalOp()); |
| RelationalOpInstr* relational_op = comparison->AsRelationalOp(); |
| RelationalOpInstr* new_relational_op = |
| new RelationalOpInstr(relational_op->token_pos(), |
| comparison->kind(), |
| left, |
| right); |
| new_relational_op->set_ic_data(relational_op->ic_data()); |
| new_comparison = new_relational_op; |
| } |
| return new BranchInstr(new_comparison, branch->is_checked()); |
| } |
| |
| |
| void BranchSimplifier::Simplify(FlowGraph* flow_graph) { |
| // Optimize some branches that test the value of a phi. When it is safe |
| // to do so, push the branch to each of the predecessor blocks. This is |
| // an optimization when (a) it can avoid materializing a boolean object at |
| // the phi only to test its value, and (b) it can expose opportunities for |
| // constant propagation and unreachable code elimination. This |
| // optimization is intended to run after inlining which creates |
| // opportunities for optimization (a) and before constant folding which |
| // can perform optimization (b). |
| |
| // Begin with a worklist of join blocks ending in branches. They are |
| // candidates for the pattern below. |
| const GrowableArray<BlockEntryInstr*>& postorder = flow_graph->postorder(); |
| GrowableArray<BlockEntryInstr*> worklist(postorder.length()); |
| for (BlockIterator it(postorder); !it.Done(); it.Advance()) { |
| BlockEntryInstr* block = it.Current(); |
| if (block->IsJoinEntry() && block->last_instruction()->IsBranch()) { |
| worklist.Add(block); |
| } |
| } |
| |
| // Rewrite until no more instance of the pattern exists. |
| bool changed = false; |
| while (!worklist.is_empty()) { |
| // All blocks in the worklist are join blocks (ending with a branch). |
| JoinEntryInstr* block = worklist.RemoveLast()->AsJoinEntry(); |
| ASSERT(block != NULL); |
| |
| if (Match(block)) { |
| changed = true; |
| |
| // The branch will be copied and pushed to all the join's |
| // predecessors. Convert the true and false target blocks into join |
| // blocks to join the control flows from all of the true |
| // (respectively, false) targets of the copied branches. |
| // |
| // The converted join block will have no phis, so it cannot be another |
| // instance of the pattern. There is thus no need to add it to the |
| // worklist. |
| BranchInstr* branch = block->last_instruction()->AsBranch(); |
| ASSERT(branch != NULL); |
| JoinEntryInstr* join_true = ToJoinEntry(branch->true_successor()); |
| JoinEntryInstr* join_false = ToJoinEntry(branch->false_successor()); |
| |
| ComparisonInstr* comparison = branch->comparison(); |
| PhiInstr* phi = comparison->left()->definition()->AsPhi(); |
| ConstantInstr* constant = comparison->right()->definition()->AsConstant(); |
| ASSERT(constant != NULL); |
| // Copy the constant and branch and push it to all the predecessors. |
| for (intptr_t i = 0, count = block->PredecessorCount(); i < count; ++i) { |
| GotoInstr* old_goto = |
| block->PredecessorAt(i)->last_instruction()->AsGoto(); |
| ASSERT(old_goto != NULL); |
| |
| // Insert a copy of the constant in all the predecessors. |
| ConstantInstr* new_constant = CloneConstant(flow_graph, constant); |
| new_constant->InsertBefore(old_goto); |
| |
| // Replace the goto in each predecessor with a rewritten branch, |
| // rewritten to use the corresponding phi input instead of the phi. |
| Value* new_left = phi->InputAt(i)->Copy(); |
| Value* new_right = new Value(new_constant); |
| BranchInstr* new_branch = CloneBranch(branch, new_left, new_right); |
| new_branch->InheritDeoptTarget(old_goto); |
| new_branch->InsertBefore(old_goto); |
| new_branch->set_next(NULL); // Detaching the goto from the graph. |
| old_goto->UnuseAllInputs(); |
| |
| // Update the predecessor block. We may have created another |
| // instance of the pattern so add it to the worklist if necessary. |
| BlockEntryInstr* branch_block = new_branch->GetBlock(); |
| branch_block->set_last_instruction(new_branch); |
| if (branch_block->IsJoinEntry()) worklist.Add(branch_block); |
| |
| // Connect the branch to the true and false joins, via empty target |
| // blocks. |
| TargetEntryInstr* true_target = |
| new TargetEntryInstr(flow_graph->max_block_id() + 1, |
| block->try_index()); |
| true_target->InheritDeoptTarget(join_true); |
| TargetEntryInstr* false_target = |
| new TargetEntryInstr(flow_graph->max_block_id() + 2, |
| block->try_index()); |
| false_target->InheritDeoptTarget(join_false); |
| flow_graph->set_max_block_id(flow_graph->max_block_id() + 2); |
| *new_branch->true_successor_address() = true_target; |
| *new_branch->false_successor_address() = false_target; |
| GotoInstr* goto_true = new GotoInstr(join_true); |
| goto_true->InheritDeoptTarget(join_true); |
| true_target->LinkTo(goto_true); |
| true_target->set_last_instruction(goto_true); |
| GotoInstr* goto_false = new GotoInstr(join_false); |
| goto_false->InheritDeoptTarget(join_false); |
| false_target->LinkTo(goto_false); |
| false_target->set_last_instruction(goto_false); |
| } |
| // When all predecessors have been rewritten, the original block is |
| // unreachable from the graph. |
| phi->UnuseAllInputs(); |
| branch->UnuseAllInputs(); |
| block->UnuseAllInputs(); |
| } |
| } |
| |
| 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); |
| } |
| } |
| |
| |
| static bool IsTrivialBlock(BlockEntryInstr* block, Definition* defn) { |
| return (block->IsTargetEntry() && (block->PredecessorCount() == 1)) && |
| ((block->next() == block->last_instruction()) || |
| ((block->next() == defn) && (defn->next() == block->last_instruction()))); |
| } |
| |
| |
| static void EliminateTrivialBlock(BlockEntryInstr* block, |
| Definition* instr, |
| IfThenElseInstr* before) { |
| block->UnuseAllInputs(); |
| block->last_instruction()->UnuseAllInputs(); |
| |
| if ((block->next() == instr) && |
| (instr->next() == block->last_instruction())) { |
| before->previous()->LinkTo(instr); |
| instr->LinkTo(before); |
| } |
| } |
| |
| |
| void IfConverter::Simplify(FlowGraph* flow_graph) { |
| if (!IfThenElseInstr::IsSupported()) { |
| return; |
| } |
| |
| bool changed = false; |
| |
| const GrowableArray<BlockEntryInstr*>& postorder = flow_graph->postorder(); |
| for (BlockIterator it(postorder); !it.Done(); it.Advance()) { |
| BlockEntryInstr* block = it.Current(); |
| JoinEntryInstr* join = block->AsJoinEntry(); |
| |
| // Detect diamond control flow pattern which materializes a value depending |
| // on the result of the comparison: |
| // |
| // B_pred: |
| // ... |
| // Branch if COMP goto (B_pred1, B_pred2) |
| // B_pred1: -- trivial block that contains at most one definition |
| // v1 = Constant(...) |
| // goto B_block |
| // B_pred2: -- trivial block that contains at most one definition |
| // v2 = Constant(...) |
| // goto B_block |
| // B_block: |
| // v3 = phi(v1, v2) -- single phi |
| // |
| // and replace it with |
| // |
| // Ba: |
| // v3 = IfThenElse(COMP ? v1 : v2) |
| // |
| if ((join != NULL) && |
| (join->phis() != NULL) && |
| (join->phis()->length() == 1) && |
| (block->PredecessorCount() == 2)) { |
| BlockEntryInstr* pred1 = block->PredecessorAt(0); |
| BlockEntryInstr* pred2 = block->PredecessorAt(1); |
| |
| PhiInstr* phi = (*join->phis())[0]; |
| Value* v1 = phi->InputAt(0); |
| Value* v2 = phi->InputAt(1); |
| |
| if (IsTrivialBlock(pred1, v1->definition()) && |
| IsTrivialBlock(pred2, v2->definition()) && |
| (pred1->PredecessorAt(0) == pred2->PredecessorAt(0))) { |
| BlockEntryInstr* pred = pred1->PredecessorAt(0); |
| BranchInstr* branch = pred->last_instruction()->AsBranch(); |
| ComparisonInstr* comparison = branch->comparison(); |
| |
| // Check if the platform supports efficient branchless IfThenElseInstr |
| // for the given combination of comparison and values flowing from |
| // false and true paths. |
| if (IfThenElseInstr::Supports(comparison, v1, v2)) { |
| Value* if_true = (pred1 == branch->true_successor()) ? v1 : v2; |
| Value* if_false = (pred2 == branch->true_successor()) ? v1 : v2; |
| |
| IfThenElseInstr* if_then_else = new IfThenElseInstr( |
| comparison->kind(), |
| comparison->InputAt(0)->Copy(), |
| comparison->InputAt(1)->Copy(), |
| if_true->Copy(), |
| if_false->Copy()); |
| flow_graph->InsertBefore(branch, |
| if_then_else, |
| NULL, |
| Definition::kValue); |
| |
| phi->ReplaceUsesWith(if_then_else); |
| |
| // Connect IfThenElseInstr to the first instruction in the merge block |
| // effectively eliminating diamond control flow. |
| // Current block as well as pred1 and pred2 blocks are no longer in |
| // the graph at this point. |
| if_then_else->LinkTo(join->next()); |
| pred->set_last_instruction(join->last_instruction()); |
| |
| // Resulting block must inherit block id from the eliminated current |
| // block to guarantee that ordering of phi operands in its successor |
| // stays consistent. |
| pred->set_block_id(block->block_id()); |
| |
| // If v1 and v2 were defined inside eliminated blocks pred1/pred2 |
| // move them out to the place before inserted IfThenElse instruction. |
| EliminateTrivialBlock(pred1, v1->definition(), if_then_else); |
| EliminateTrivialBlock(pred2, v2->definition(), if_then_else); |
| |
| // Update use lists to reflect changes in the graph. |
| phi->UnuseAllInputs(); |
| branch->UnuseAllInputs(); |
| |
| // The graph has changed. Recompute dominators and block orders after |
| // this pass is finished. |
| changed = true; |
| } |
| } |
| } |
| } |
| |
| 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 |