| // Copyright (c) 2020, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| #include "vm/compiler/backend/flow_graph.h" |
| #include "vm/compiler/compiler_pass.h" |
| #include "vm/compiler/write_barrier_elimination.h" |
| |
| namespace dart { |
| |
| #if defined(DEBUG) |
| DEFINE_FLAG(bool, |
| trace_write_barrier_elimination, |
| false, |
| "Trace WriteBarrierElimination pass."); |
| #endif |
| |
| class DefinitionIndexPairTrait { |
| public: |
| typedef Definition* Key; |
| typedef intptr_t Value; |
| struct Pair { |
| Definition* definition = nullptr; |
| intptr_t index = -1; |
| Pair() {} |
| Pair(Definition* definition, intptr_t index) |
| : definition(definition), index(index) {} |
| }; |
| |
| static Key KeyOf(Pair kv) { return kv.definition; } |
| static Value ValueOf(Pair kv) { return kv.index; } |
| static inline uword Hash(Key key) { |
| return Utils::WordHash(reinterpret_cast<intptr_t>(key)); |
| } |
| static inline bool IsKeyEqual(Pair kv, Key key) { |
| return kv.definition == key; |
| } |
| }; |
| |
| typedef DirectChainedHashMap<DefinitionIndexPairTrait> DefinitionIndexMap; |
| |
| // Inter-block write-barrier elimination. |
| // |
| // This optimization removes write barriers from some store instructions under |
| // certain assumptions which the runtime is responsible to sustain. |
| // |
| // We can skip a write barrier on a StoreInstanceField to a container object X |
| // if we know that either: |
| // - X is in new-space, or |
| // - X is in old-space, and: |
| // - X is in the store buffer, and |
| // - X is in the deferred marking stack (if concurrent marking is enabled) |
| // |
| // The result of an Allocation instruction (Instruction::IsAllocation()) will |
| // satisfy one of these requirements immediately after the instruction |
| // if WillAllocateNewOrRemembered() is true. |
| // |
| // Without runtime support, we would have to assume that any instruction which |
| // can trigger a new-space scavenge (Instruction::CanTriggerGC()) might promote |
| // a new-space temporary into old-space, and we could not skip a store barrier |
| // on a write into it afterward. |
| // |
| // However, many instructions can trigger GC in unlikely cases, like |
| // CheckStackOverflow and Box. To avoid interrupting write barrier elimination |
| // across these instructions, the runtime ensures that any live temporaries |
| // (except arrays) promoted during a scavenge caused by a non-Dart-call |
| // instruction (see Instruction::CanCallDart()) will be added to the store |
| // buffer. Additionally, if concurrent marking was initiated, the runtime |
| // ensures that all live temporaries are also in the deferred marking stack. |
| // |
| // See also Thread::RememberLiveTemporaries() and |
| // Thread::DeferredMarkLiveTemporaries(). |
| class WriteBarrierElimination : public ValueObject { |
| public: |
| WriteBarrierElimination(Zone* zone, FlowGraph* flow_graph); |
| |
| void Analyze(); |
| void SaveResults(); |
| |
| private: |
| void IndexDefinitions(Zone* zone); |
| |
| bool AnalyzeBlock(BlockEntryInstr* entry); |
| void MergePredecessors(BlockEntryInstr* entry); |
| |
| void UpdateVectorForBlock(BlockEntryInstr* entry, bool finalize); |
| |
| static intptr_t Index(BlockEntryInstr* entry) { |
| return entry->postorder_number(); |
| } |
| |
| intptr_t Index(Definition* def) { |
| ASSERT(IsUsable(def)); |
| return definition_indices_.LookupValue(def); |
| } |
| |
| bool IsUsable(Definition* def) { |
| return def->IsPhi() || (def->IsAllocation() && |
| def->AsAllocation()->WillAllocateNewOrRemembered()); |
| } |
| |
| #if defined(DEBUG) |
| static bool SlotEligibleForWBE(const Slot& slot); |
| #endif |
| |
| FlowGraph* const flow_graph_; |
| const GrowableArray<BlockEntryInstr*>* const block_order_; |
| |
| // Number of usable definitions in the graph. |
| intptr_t definition_count_ = 0; |
| |
| // Maps each usable definition to its index in the bitvectors. |
| DefinitionIndexMap definition_indices_; |
| |
| // Bitvector with all non-Array-allocation instructions set. Used to |
| // un-mark Array allocations as usable. |
| BitVector* large_array_allocations_mask_; |
| |
| // Bitvectors for each block of which allocations are new or remembered |
| // at the start (after Phis). |
| GrowableArray<BitVector*> usable_allocs_in_; |
| |
| // Bitvectors for each block of which allocations are new or remembered |
| // at the end of the block. |
| GrowableArray<BitVector*> usable_allocs_out_; |
| |
| // Remaining blocks to process. |
| GrowableArray<BlockEntryInstr*> worklist_; |
| |
| // Temporary used in many functions to avoid repeated zone allocation. |
| BitVector* vector_; |
| |
| // Bitvector of blocks which have been processed, to ensure each block |
| // is processed at least once. |
| BitVector* processed_blocks_; |
| |
| #if defined(DEBUG) |
| bool tracing_ = false; |
| #else |
| static constexpr bool tracing_ = false; |
| #endif |
| }; |
| |
| WriteBarrierElimination::WriteBarrierElimination(Zone* zone, |
| FlowGraph* flow_graph) |
| : flow_graph_(flow_graph), block_order_(&flow_graph->postorder()) { |
| #if defined(DEBUG) |
| if (flow_graph->should_print() && FLAG_trace_write_barrier_elimination) { |
| tracing_ = true; |
| } |
| #endif |
| |
| IndexDefinitions(zone); |
| |
| for (intptr_t i = 0; i < block_order_->length(); ++i) { |
| usable_allocs_in_.Add(new (zone) BitVector(zone, definition_count_)); |
| usable_allocs_in_[i]->CopyFrom(vector_); |
| |
| usable_allocs_out_.Add(new (zone) BitVector(zone, definition_count_)); |
| usable_allocs_out_[i]->CopyFrom(vector_); |
| } |
| |
| processed_blocks_ = new (zone) BitVector(zone, block_order_->length()); |
| } |
| |
| void WriteBarrierElimination::Analyze() { |
| for (intptr_t i = 0; i < block_order_->length(); ++i) { |
| worklist_.Add(block_order_->At(i)); |
| } |
| |
| while (!worklist_.is_empty()) { |
| auto* const entry = worklist_.RemoveLast(); |
| if (AnalyzeBlock(entry)) { |
| for (intptr_t i = 0; i < entry->last_instruction()->SuccessorCount(); |
| ++i) { |
| if (tracing_) { |
| THR_Print("Enqueueing block %" Pd "\n", entry->block_id()); |
| } |
| worklist_.Add(entry->last_instruction()->SuccessorAt(i)); |
| } |
| } |
| } |
| } |
| |
| void WriteBarrierElimination::SaveResults() { |
| for (intptr_t i = 0; i < block_order_->length(); ++i) { |
| vector_->CopyFrom(usable_allocs_in_[i]); |
| UpdateVectorForBlock(block_order_->At(i), /*finalize=*/true); |
| } |
| } |
| |
| static bool IsCreateLargeArray(Definition* defn) { |
| if (auto create_array = defn->AsCreateArray()) { |
| static_assert(!Array::UseCardMarkingForAllocation( |
| Array::kMaxLengthForWriteBarrierElimination), |
| "Invariant restoration code does not handle card marking."); |
| // Note: IsUsable would reject CreateArray instructions with non-constant |
| // number of elements. |
| return create_array->GetConstantNumElements() > |
| Array::kMaxLengthForWriteBarrierElimination; |
| } |
| return false; |
| } |
| |
| void WriteBarrierElimination::IndexDefinitions(Zone* zone) { |
| BitmapBuilder large_array_allocations; |
| |
| GrowableArray<Definition*> create_array_worklist; |
| |
| for (intptr_t i = 0; i < block_order_->length(); ++i) { |
| BlockEntryInstr* const block = block_order_->At(i); |
| if (auto join_block = block->AsJoinEntry()) { |
| for (PhiIterator it(join_block); !it.Done(); it.Advance()) { |
| large_array_allocations.Set(definition_count_, false); |
| definition_indices_.Insert({it.Current(), definition_count_++}); |
| #if defined(DEBUG) |
| if (tracing_) { |
| THR_Print("Definition (%" Pd ") has index %" Pd ".\n", |
| it.Current()->ssa_temp_index(), definition_count_ - 1); |
| } |
| #endif |
| } |
| } |
| for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) { |
| if (Definition* current = it.Current()->AsDefinition()) { |
| if (IsUsable(current)) { |
| const bool is_create_large_array = IsCreateLargeArray(current); |
| large_array_allocations.Set(definition_count_, is_create_large_array); |
| definition_indices_.Insert({current, definition_count_++}); |
| if (is_create_large_array) { |
| create_array_worklist.Add(current); |
| } |
| #if defined(DEBUG) |
| if (tracing_) { |
| THR_Print("Definition (%" Pd ") has index %" Pd ".\n", |
| current->ssa_temp_index(), definition_count_ - 1); |
| } |
| #endif |
| } |
| } |
| } |
| } |
| |
| while (!create_array_worklist.is_empty()) { |
| auto instr = create_array_worklist.RemoveLast(); |
| for (Value::Iterator it(instr->input_use_list()); !it.Done(); |
| it.Advance()) { |
| if (auto phi_use = it.Current()->instruction()->AsPhi()) { |
| const intptr_t index = Index(phi_use); |
| if (!large_array_allocations.Get(index)) { |
| large_array_allocations.Set(index, |
| /*can_be_create_large_array=*/true); |
| create_array_worklist.Add(phi_use); |
| } |
| } |
| } |
| } |
| |
| vector_ = new (zone) BitVector(zone, definition_count_); |
| vector_->SetAll(); |
| large_array_allocations_mask_ = new (zone) BitVector(zone, definition_count_); |
| for (intptr_t i = 0; i < definition_count_; ++i) { |
| if (!large_array_allocations.Get(i)) large_array_allocations_mask_->Add(i); |
| } |
| } |
| |
| void WriteBarrierElimination::MergePredecessors(BlockEntryInstr* entry) { |
| vector_->Clear(); |
| for (intptr_t i = 0; i < entry->PredecessorCount(); ++i) { |
| BitVector* predecessor_set = |
| usable_allocs_out_[Index(entry->PredecessorAt(i))]; |
| if (i == 0) { |
| vector_->AddAll(predecessor_set); |
| } else { |
| vector_->Intersect(predecessor_set); |
| } |
| } |
| |
| if (JoinEntryInstr* join = entry->AsJoinEntry()) { |
| // A Phi is usable if and only if all its inputs are usable. |
| for (PhiIterator it(join); !it.Done(); it.Advance()) { |
| PhiInstr* phi = it.Current(); |
| ASSERT(phi->InputCount() == entry->PredecessorCount()); |
| bool is_usable = true; |
| for (intptr_t i = 0; i < phi->InputCount(); ++i) { |
| BitVector* const predecessor_set = |
| usable_allocs_out_[Index(entry->PredecessorAt(i))]; |
| Definition* const origin = phi->InputAt(i)->definition(); |
| if (!IsUsable(origin) || !predecessor_set->Contains(Index(origin))) { |
| is_usable = false; |
| break; |
| } |
| } |
| vector_->Set(Index(phi), is_usable); |
| } |
| |
| #if defined(DEBUG) |
| if (tracing_) { |
| THR_Print("Merge predecessors for %" Pd ".\n", entry->block_id()); |
| for (PhiIterator it(join); !it.Done(); it.Advance()) { |
| PhiInstr* phi = it.Current(); |
| THR_Print("%" Pd ": %s\n", phi->ssa_temp_index(), |
| vector_->Contains(Index(phi)) ? "true" : "false"); |
| } |
| } |
| #endif |
| } |
| } |
| |
| bool WriteBarrierElimination::AnalyzeBlock(BlockEntryInstr* entry) { |
| // Recompute the usable allocs in-set. |
| MergePredecessors(entry); |
| |
| // If the in-set has not changed, there's no work to do. |
| BitVector* const in_set = usable_allocs_in_[Index(entry)]; |
| ASSERT(vector_->SubsetOf(*in_set)); // convergence |
| if (vector_->Equals(*in_set) && processed_blocks_->Contains(Index(entry))) { |
| if (tracing_) { |
| THR_Print("Bailout of block %" Pd ": inputs didn't change.\n", |
| entry->block_id()); |
| } |
| return false; |
| } else if (tracing_) { |
| THR_Print("Inputs of block %" Pd " changed: ", entry->block_id()); |
| in_set->Print(); |
| THR_Print(" -> "); |
| vector_->Print(); |
| THR_Print("\n"); |
| } |
| |
| usable_allocs_in_[Index(entry)]->CopyFrom(vector_); |
| UpdateVectorForBlock(entry, /*finalize=*/false); |
| |
| processed_blocks_->Add(Index(entry)); |
| |
| // Successors only need to be updated if the out-set changes. |
| if (vector_->Equals(*usable_allocs_out_[Index(entry)])) { |
| if (tracing_) { |
| THR_Print("Bailout of block %" Pd ": out-set didn't change.\n", |
| entry->block_id()); |
| } |
| return false; |
| } |
| |
| BitVector* const out_set = usable_allocs_out_[Index(entry)]; |
| ASSERT(vector_->SubsetOf(*out_set)); // convergence |
| out_set->CopyFrom(vector_); |
| if (tracing_) { |
| THR_Print("Block %" Pd " changed.\n", entry->block_id()); |
| } |
| return true; |
| } |
| |
| #if defined(DEBUG) |
| bool WriteBarrierElimination::SlotEligibleForWBE(const Slot& slot) { |
| // We assume that Dart code only stores into Instances, Contexts, and |
| // UnhandledExceptions. This assumption is used in |
| // RestoreWriteBarrierInvariantVisitor::VisitPointers. |
| |
| switch (slot.kind()) { |
| case Slot::Kind::kCapturedVariable: // Context |
| return true; |
| case Slot::Kind::kDartField: // Instance |
| return true; |
| |
| #define FOR_EACH_NATIVE_SLOT(class, underlying_type, field, __, ___) \ |
| case Slot::Kind::k##class##_##field: \ |
| return std::is_base_of<UntaggedInstance, underlying_type>::value || \ |
| std::is_base_of<UntaggedContext, underlying_type>::value || \ |
| std::is_base_of<UntaggedUnhandledException, \ |
| underlying_type>::value; |
| |
| NATIVE_SLOTS_LIST(FOR_EACH_NATIVE_SLOT) |
| #undef FOR_EACH_NATIVE_SLOT |
| |
| default: |
| return false; |
| } |
| } |
| #endif |
| |
| void WriteBarrierElimination::UpdateVectorForBlock(BlockEntryInstr* entry, |
| bool finalize) { |
| for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) { |
| Instruction* const current = it.Current(); |
| |
| if (finalize) { |
| if (StoreInstanceFieldInstr* instr = current->AsStoreInstanceField()) { |
| Definition* const container = instr->instance()->definition(); |
| if (IsUsable(container) && vector_->Contains(Index(container))) { |
| DEBUG_ASSERT(SlotEligibleForWBE(instr->slot())); |
| instr->set_emit_store_barrier(kNoStoreBarrier); |
| } |
| } else if (StoreIndexedInstr* instr = current->AsStoreIndexed()) { |
| Definition* const array = instr->array()->definition(); |
| if (IsUsable(array) && vector_->Contains(Index(array))) { |
| instr->set_emit_store_barrier(StoreBarrierType::kNoStoreBarrier); |
| } |
| } |
| } |
| |
| if (current->CanCallDart()) { |
| vector_->Clear(); |
| } else if (current->CanTriggerGC()) { |
| // Clear large array allocations. These are not added to the remembered |
| // set by Thread::RememberLiveTemporaries() after a scavenge. |
| vector_->Intersect(large_array_allocations_mask_); |
| } |
| |
| if (AllocationInstr* const alloc = current->AsAllocation()) { |
| if (alloc->WillAllocateNewOrRemembered()) { |
| vector_->Add(Index(alloc)); |
| } |
| } |
| } |
| } |
| |
| void EliminateWriteBarriers(FlowGraph* flow_graph) { |
| WriteBarrierElimination elimination(Thread::Current()->zone(), flow_graph); |
| elimination.Analyze(); |
| elimination.SaveResults(); |
| } |
| |
| } // namespace dart |