From f39d585900ff280e492999148b1b426f3175f43b Mon Sep 17 00:00:00 2001 From: "svenpanne@chromium.org" Date: Fri, 23 May 2014 07:48:22 +0000 Subject: [PATCH] Use the flow engine for HMergeRemovableSimulatesPhase. For now, this is a 1:1 reformulation of the block-local analysis, but this will change. R=bmeurer@chromium.org Review URL: https://codereview.chromium.org/294473015 git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@21452 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/flag-definitions.h | 1 + src/hydrogen-removable-simulates.cc | 191 +++++++++++++++++++++++------------- 2 files changed, 126 insertions(+), 66 deletions(-) diff --git a/src/flag-definitions.h b/src/flag-definitions.h index a563c33..b5077c7 100644 --- a/src/flag-definitions.h +++ b/src/flag-definitions.h @@ -259,6 +259,7 @@ DEFINE_bool(trace_all_uses, false, "trace all use positions") DEFINE_bool(trace_range, false, "trace range analysis") DEFINE_bool(trace_gvn, false, "trace global value numbering") DEFINE_bool(trace_representation, false, "trace representation types") +DEFINE_bool(trace_removable_simulates, false, "trace removable simulates") DEFINE_bool(trace_escape_analysis, false, "trace hydrogen escape analysis") DEFINE_bool(trace_allocation_folding, false, "trace allocation folding") DEFINE_bool(trace_track_allocation_sites, false, diff --git a/src/hydrogen-removable-simulates.cc b/src/hydrogen-removable-simulates.cc index 7bbe3cb..738c735 100644 --- a/src/hydrogen-removable-simulates.cc +++ b/src/hydrogen-removable-simulates.cc @@ -2,84 +2,143 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. +#include "hydrogen-flow-engine.h" +#include "hydrogen-instructions.h" #include "hydrogen-removable-simulates.h" namespace v8 { namespace internal { -void HMergeRemovableSimulatesPhase::Run() { - ZoneList mergelist(2, zone()); - for (int i = 0; i < graph()->blocks()->length(); ++i) { - HBasicBlock* block = graph()->blocks()->at(i); +class State : public ZoneObject { + public: + explicit State(Zone* zone) + : zone_(zone), mergelist_(2, zone), first_(true), mode_(NORMAL) { } + + State* Process(HInstruction* instr, Zone* zone) { + if (FLAG_trace_removable_simulates) { + PrintF("[State::Process %s #%d %s]\n", + mode_ == NORMAL ? "normal" : "collect", + instr->id(), instr->Mnemonic()); + } + // Forward-merge "trains" of simulates after an instruction with observable + // side effects to keep live ranges short. + if (mode_ == COLLECT_CONSECUTIVE_SIMULATES) { + if (instr->IsSimulate()) { + HSimulate* current_simulate = HSimulate::cast(instr); + if (current_simulate->is_candidate_for_removal() && + !current_simulate->ast_id().IsNone()) { + Remember(current_simulate); + return this; + } + } + FlushSimulates(); + mode_ = NORMAL; + } + // Ensure there's a non-foldable HSimulate before an HEnterInlined to avoid + // folding across HEnterInlined. + ASSERT(!(instr->IsEnterInlined() && + HSimulate::cast(instr->previous())->is_candidate_for_removal())); + if (instr->IsLeaveInlined() || instr->IsReturn()) { + // Never fold simulates from inlined environments into simulates in the + // outer environment. Simply remove all accumulated simulates without + // merging. This is safe because simulates after instructions with side + // effects are never added to the merge list. The same reasoning holds for + // return instructions. + RemoveSimulates(); + return this; + } + if (instr->IsControlInstruction()) { + // Merge the accumulated simulates at the end of the block. + FlushSimulates(); + return this; + } + // Skip the non-simulates and the first simulate. + if (!instr->IsSimulate()) return this; + if (first_) { + first_ = false; + return this; + } + HSimulate* current_simulate = HSimulate::cast(instr); + if (!current_simulate->is_candidate_for_removal()) { + Remember(current_simulate); + FlushSimulates(); + } else if (current_simulate->ast_id().IsNone()) { + ASSERT(current_simulate->next()->IsEnterInlined()); + FlushSimulates(); + } else if (current_simulate->previous()->HasObservableSideEffects()) { + Remember(current_simulate); + mode_ = COLLECT_CONSECUTIVE_SIMULATES; + } else { + Remember(current_simulate); + } + + return this; + } + + static State* Merge(State* succ_state, + HBasicBlock* succ_block, + State* pred_state, + HBasicBlock* pred_block, + Zone* zone) { + if (FLAG_trace_removable_simulates) { + PrintF("[State::Merge predecessor block %d, successor block %d\n", + pred_block->block_id(), succ_block->block_id()); + } + return pred_state; + } + + static State* Finish(State* state, HBasicBlock* block, Zone* zone) { + if (FLAG_trace_removable_simulates) { + PrintF("[State::Finish block %d]\n", block->block_id()); } // Make sure the merge list is empty at the start of a block. - ASSERT(mergelist.is_empty()); + ASSERT(state->mergelist_.is_empty()); // Nasty heuristic: Never remove the first simulate in a block. This // just so happens to have a beneficial effect on register allocation. - bool first = true; - for (HInstructionIterator it(block); !it.Done(); it.Advance()) { - HInstruction* current = it.Current(); - if (current->IsEnterInlined()) { - // Ensure there's a non-foldable HSimulate before an HEnterInlined to - // avoid folding across HEnterInlined. - ASSERT(!HSimulate::cast(current->previous())-> - is_candidate_for_removal()); - } - if (current->IsLeaveInlined()) { - // Never fold simulates from inlined environments into simulates in the - // outer environment. Simply remove all accumulated simulates without - // merging. This is safe because simulates after instructions with side - // effects are never added to the merge list. - while (!mergelist.is_empty()) { - mergelist.RemoveLast()->DeleteAndReplaceWith(NULL); - } - continue; - } - if (current->IsReturn()) { - // Drop mergeable simulates in the list. This is safe because - // simulates after instructions with side effects are never added - // to the merge list. - while (!mergelist.is_empty()) { - mergelist.RemoveLast()->DeleteAndReplaceWith(NULL); - } - continue; - } - // Skip the non-simulates and the first simulate. - if (!current->IsSimulate()) continue; - if (first) { - first = false; - continue; - } - HSimulate* current_simulate = HSimulate::cast(current); - if (!current_simulate->is_candidate_for_removal()) { - current_simulate->MergeWith(&mergelist); - } else if (current_simulate->ast_id().IsNone()) { - ASSERT(current_simulate->next()->IsEnterInlined()); - if (!mergelist.is_empty()) { - HSimulate* last = mergelist.RemoveLast(); - last->MergeWith(&mergelist); - } - } else if (current_simulate->previous()->HasObservableSideEffects()) { - while (current_simulate->next()->IsSimulate()) { - it.Advance(); - HSimulate* next_simulate = HSimulate::cast(it.Current()); - if (next_simulate->ast_id().IsNone()) break; - mergelist.Add(current_simulate, zone()); - current_simulate = next_simulate; - if (!current_simulate->is_candidate_for_removal()) break; - } - current_simulate->MergeWith(&mergelist); - } else { - // Accumulate this simulate for folding later on. - mergelist.Add(current_simulate, zone()); - } + state->first_ = true; + return state; + } + + private: + enum Mode { NORMAL, COLLECT_CONSECUTIVE_SIMULATES }; + + void Remember(HSimulate* sim) { + mergelist_.Add(sim, zone_); + } + + void FlushSimulates() { + if (!mergelist_.is_empty()) { + mergelist_.RemoveLast()->MergeWith(&mergelist_); } + } - if (!mergelist.is_empty()) { - // Merge the accumulated simulates at the end of the block. - HSimulate* last = mergelist.RemoveLast(); - last->MergeWith(&mergelist); + void RemoveSimulates() { + while (!mergelist_.is_empty()) { + mergelist_.RemoveLast()->DeleteAndReplaceWith(NULL); } } + + Zone* zone_; + ZoneList mergelist_; + bool first_; + Mode mode_; +}; + + +// We don't use effects here. +class Effects : public ZoneObject { + public: + explicit Effects(Zone* zone) { } + bool Disabled() { return true; } + void Process(HInstruction* instr, Zone* zone) { } + void Apply(State* state) { } + void Union(Effects* that, Zone* zone) { } +}; + + +void HMergeRemovableSimulatesPhase::Run() { + HFlowEngine engine(graph(), zone()); + State* state = new(zone()) State(zone()); + engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), state); } } } // namespace v8::internal -- 2.7.4