// Copyright 2013 the V8 project authors. All rights reserved. // Redistribution and use in source and binary forms, with or without // modification, are permitted provided that the following conditions are // met: // // * Redistributions of source code must retain the above copyright // notice, this list of conditions and the following disclaimer. // * Redistributions in binary form must reproduce the above // copyright notice, this list of conditions and the following // disclaimer in the documentation and/or other materials provided // with the distribution. // * Neither the name of Google Inc. nor the names of its // contributors may be used to endorse or promote products derived // from this software without specific prior written permission. // // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include "hydrogen.h" #include "hydrogen-gvn.h" #include "v8.h" namespace v8 { namespace internal { class HValueMap: public ZoneObject { public: explicit HValueMap(Zone* zone) : array_size_(0), lists_size_(0), count_(0), present_flags_(0), array_(NULL), lists_(NULL), free_list_head_(kNil) { ResizeLists(kInitialSize, zone); Resize(kInitialSize, zone); } void Kill(GVNFlagSet flags); void Add(HValue* value, Zone* zone) { present_flags_.Add(value->gvn_flags()); Insert(value, zone); } HValue* Lookup(HValue* value) const; HValueMap* Copy(Zone* zone) const { return new(zone) HValueMap(zone, this); } bool IsEmpty() const { return count_ == 0; } private: // A linked list of HValue* values. Stored in arrays. struct HValueMapListElement { HValue* value; int next; // Index in the array of the next list element. }; static const int kNil = -1; // The end of a linked list // Must be a power of 2. static const int kInitialSize = 16; HValueMap(Zone* zone, const HValueMap* other); void Resize(int new_size, Zone* zone); void ResizeLists(int new_size, Zone* zone); void Insert(HValue* value, Zone* zone); uint32_t Bound(uint32_t value) const { return value & (array_size_ - 1); } int array_size_; int lists_size_; int count_; // The number of values stored in the HValueMap. GVNFlagSet present_flags_; // All flags that are in any value in the // HValueMap. HValueMapListElement* array_; // Primary store - contains the first value // with a given hash. Colliding elements are stored in linked lists. HValueMapListElement* lists_; // The linked lists containing hash collisions. int free_list_head_; // Unused elements in lists_ are on the free list. }; class HSideEffectMap BASE_EMBEDDED { public: HSideEffectMap(); explicit HSideEffectMap(HSideEffectMap* other); HSideEffectMap& operator= (const HSideEffectMap& other); void Kill(GVNFlagSet flags); void Store(GVNFlagSet flags, HInstruction* instr); bool IsEmpty() const { return count_ == 0; } inline HInstruction* operator[](int i) const { ASSERT(0 <= i); ASSERT(i < kNumberOfTrackedSideEffects); return data_[i]; } inline HInstruction* at(int i) const { return operator[](i); } private: int count_; HInstruction* data_[kNumberOfTrackedSideEffects]; }; void TraceGVN(const char* msg, ...) { va_list arguments; va_start(arguments, msg); OS::VPrint(msg, arguments); va_end(arguments); } // Wrap TraceGVN in macros to avoid the expense of evaluating its arguments when // --trace-gvn is off. #define TRACE_GVN_1(msg, a1) \ if (FLAG_trace_gvn) { \ TraceGVN(msg, a1); \ } #define TRACE_GVN_2(msg, a1, a2) \ if (FLAG_trace_gvn) { \ TraceGVN(msg, a1, a2); \ } #define TRACE_GVN_3(msg, a1, a2, a3) \ if (FLAG_trace_gvn) { \ TraceGVN(msg, a1, a2, a3); \ } #define TRACE_GVN_4(msg, a1, a2, a3, a4) \ if (FLAG_trace_gvn) { \ TraceGVN(msg, a1, a2, a3, a4); \ } #define TRACE_GVN_5(msg, a1, a2, a3, a4, a5) \ if (FLAG_trace_gvn) { \ TraceGVN(msg, a1, a2, a3, a4, a5); \ } HValueMap::HValueMap(Zone* zone, const HValueMap* other) : array_size_(other->array_size_), lists_size_(other->lists_size_), count_(other->count_), present_flags_(other->present_flags_), array_(zone->NewArray<HValueMapListElement>(other->array_size_)), lists_(zone->NewArray<HValueMapListElement>(other->lists_size_)), free_list_head_(other->free_list_head_) { OS::MemCopy( array_, other->array_, array_size_ * sizeof(HValueMapListElement)); OS::MemCopy( lists_, other->lists_, lists_size_ * sizeof(HValueMapListElement)); } void HValueMap::Kill(GVNFlagSet flags) { GVNFlagSet depends_flags = HValue::ConvertChangesToDependsFlags(flags); if (!present_flags_.ContainsAnyOf(depends_flags)) return; present_flags_.RemoveAll(); for (int i = 0; i < array_size_; ++i) { HValue* value = array_[i].value; if (value != NULL) { // Clear list of collisions first, so we know if it becomes empty. int kept = kNil; // List of kept elements. int next; for (int current = array_[i].next; current != kNil; current = next) { next = lists_[current].next; HValue* value = lists_[current].value; if (value->gvn_flags().ContainsAnyOf(depends_flags)) { // Drop it. count_--; lists_[current].next = free_list_head_; free_list_head_ = current; } else { // Keep it. lists_[current].next = kept; kept = current; present_flags_.Add(value->gvn_flags()); } } array_[i].next = kept; // Now possibly drop directly indexed element. value = array_[i].value; if (value->gvn_flags().ContainsAnyOf(depends_flags)) { // Drop it. count_--; int head = array_[i].next; if (head == kNil) { array_[i].value = NULL; } else { array_[i].value = lists_[head].value; array_[i].next = lists_[head].next; lists_[head].next = free_list_head_; free_list_head_ = head; } } else { present_flags_.Add(value->gvn_flags()); // Keep it. } } } } HValue* HValueMap::Lookup(HValue* value) const { uint32_t hash = static_cast<uint32_t>(value->Hashcode()); uint32_t pos = Bound(hash); if (array_[pos].value != NULL) { if (array_[pos].value->Equals(value)) return array_[pos].value; int next = array_[pos].next; while (next != kNil) { if (lists_[next].value->Equals(value)) return lists_[next].value; next = lists_[next].next; } } return NULL; } void HValueMap::Resize(int new_size, Zone* zone) { ASSERT(new_size > count_); // Hashing the values into the new array has no more collisions than in the // old hash map, so we can use the existing lists_ array, if we are careful. // Make sure we have at least one free element. if (free_list_head_ == kNil) { ResizeLists(lists_size_ << 1, zone); } HValueMapListElement* new_array = zone->NewArray<HValueMapListElement>(new_size); memset(new_array, 0, sizeof(HValueMapListElement) * new_size); HValueMapListElement* old_array = array_; int old_size = array_size_; int old_count = count_; count_ = 0; // Do not modify present_flags_. It is currently correct. array_size_ = new_size; array_ = new_array; if (old_array != NULL) { // Iterate over all the elements in lists, rehashing them. for (int i = 0; i < old_size; ++i) { if (old_array[i].value != NULL) { int current = old_array[i].next; while (current != kNil) { Insert(lists_[current].value, zone); int next = lists_[current].next; lists_[current].next = free_list_head_; free_list_head_ = current; current = next; } // Rehash the directly stored value. Insert(old_array[i].value, zone); } } } USE(old_count); ASSERT(count_ == old_count); } void HValueMap::ResizeLists(int new_size, Zone* zone) { ASSERT(new_size > lists_size_); HValueMapListElement* new_lists = zone->NewArray<HValueMapListElement>(new_size); memset(new_lists, 0, sizeof(HValueMapListElement) * new_size); HValueMapListElement* old_lists = lists_; int old_size = lists_size_; lists_size_ = new_size; lists_ = new_lists; if (old_lists != NULL) { OS::MemCopy(lists_, old_lists, old_size * sizeof(HValueMapListElement)); } for (int i = old_size; i < lists_size_; ++i) { lists_[i].next = free_list_head_; free_list_head_ = i; } } void HValueMap::Insert(HValue* value, Zone* zone) { ASSERT(value != NULL); // Resizing when half of the hashtable is filled up. if (count_ >= array_size_ >> 1) Resize(array_size_ << 1, zone); ASSERT(count_ < array_size_); count_++; uint32_t pos = Bound(static_cast<uint32_t>(value->Hashcode())); if (array_[pos].value == NULL) { array_[pos].value = value; array_[pos].next = kNil; } else { if (free_list_head_ == kNil) { ResizeLists(lists_size_ << 1, zone); } int new_element_pos = free_list_head_; ASSERT(new_element_pos != kNil); free_list_head_ = lists_[free_list_head_].next; lists_[new_element_pos].value = value; lists_[new_element_pos].next = array_[pos].next; ASSERT(array_[pos].next == kNil || lists_[array_[pos].next].value != NULL); array_[pos].next = new_element_pos; } } HSideEffectMap::HSideEffectMap() : count_(0) { memset(data_, 0, kNumberOfTrackedSideEffects * kPointerSize); } HSideEffectMap::HSideEffectMap(HSideEffectMap* other) : count_(other->count_) { *this = *other; // Calls operator=. } HSideEffectMap& HSideEffectMap::operator= (const HSideEffectMap& other) { if (this != &other) { OS::MemCopy(data_, other.data_, kNumberOfTrackedSideEffects * kPointerSize); } return *this; } void HSideEffectMap::Kill(GVNFlagSet flags) { for (int i = 0; i < kNumberOfTrackedSideEffects; i++) { GVNFlag changes_flag = HValue::ChangesFlagFromInt(i); if (flags.Contains(changes_flag)) { if (data_[i] != NULL) count_--; data_[i] = NULL; } } } void HSideEffectMap::Store(GVNFlagSet flags, HInstruction* instr) { for (int i = 0; i < kNumberOfTrackedSideEffects; i++) { GVNFlag changes_flag = HValue::ChangesFlagFromInt(i); if (flags.Contains(changes_flag)) { if (data_[i] == NULL) count_++; data_[i] = instr; } } } HGlobalValueNumberingPhase::HGlobalValueNumberingPhase(HGraph* graph) : HPhase("H_Global value numbering", graph), removed_side_effects_(false), block_side_effects_(graph->blocks()->length(), zone()), loop_side_effects_(graph->blocks()->length(), zone()), visited_on_paths_(graph->blocks()->length(), zone()) { ASSERT(!AllowHandleAllocation::IsAllowed()); block_side_effects_.AddBlock(GVNFlagSet(), graph->blocks()->length(), zone()); loop_side_effects_.AddBlock(GVNFlagSet(), graph->blocks()->length(), zone()); } void HGlobalValueNumberingPhase::Analyze() { removed_side_effects_ = false; ComputeBlockSideEffects(); if (FLAG_loop_invariant_code_motion) { LoopInvariantCodeMotion(); } AnalyzeGraph(); } void HGlobalValueNumberingPhase::ComputeBlockSideEffects() { // The Analyze phase of GVN can be called multiple times. Clear loop side // effects before computing them to erase the contents from previous Analyze // passes. for (int i = 0; i < loop_side_effects_.length(); ++i) { loop_side_effects_[i].RemoveAll(); } for (int i = graph()->blocks()->length() - 1; i >= 0; --i) { // Compute side effects for the block. HBasicBlock* block = graph()->blocks()->at(i); GVNFlagSet side_effects; if (block->IsReachable() && !block->IsDeoptimizing()) { int id = block->block_id(); for (HInstructionIterator it(block); !it.Done(); it.Advance()) { HInstruction* instr = it.Current(); side_effects.Add(instr->ChangesFlags()); } block_side_effects_[id].Add(side_effects); // Loop headers are part of their loop. if (block->IsLoopHeader()) { loop_side_effects_[id].Add(side_effects); } // Propagate loop side effects upwards. if (block->HasParentLoopHeader()) { int header_id = block->parent_loop_header()->block_id(); loop_side_effects_[header_id].Add(block->IsLoopHeader() ? loop_side_effects_[id] : side_effects); } } } } SmartArrayPointer<char> GetGVNFlagsString(GVNFlagSet flags) { char underlying_buffer[kLastFlag * 128]; Vector<char> buffer(underlying_buffer, sizeof(underlying_buffer)); #if DEBUG int offset = 0; const char* separator = ""; const char* comma = ", "; buffer[0] = 0; uint32_t set_depends_on = 0; uint32_t set_changes = 0; for (int bit = 0; bit < kLastFlag; ++bit) { if ((flags.ToIntegral() & (1 << bit)) != 0) { if (bit % 2 == 0) { set_changes++; } else { set_depends_on++; } } } bool positive_changes = set_changes < (kLastFlag / 2); bool positive_depends_on = set_depends_on < (kLastFlag / 2); if (set_changes > 0) { if (positive_changes) { offset += OS::SNPrintF(buffer + offset, "changes ["); } else { offset += OS::SNPrintF(buffer + offset, "changes all except ["); } for (int bit = 0; bit < kLastFlag; ++bit) { if (((flags.ToIntegral() & (1 << bit)) != 0) == positive_changes) { switch (static_cast<GVNFlag>(bit)) { #define DECLARE_FLAG(type) \ case kChanges##type: \ offset += OS::SNPrintF(buffer + offset, separator); \ offset += OS::SNPrintF(buffer + offset, #type); \ separator = comma; \ break; GVN_TRACKED_FLAG_LIST(DECLARE_FLAG) GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG) #undef DECLARE_FLAG default: break; } } } offset += OS::SNPrintF(buffer + offset, "]"); } if (set_depends_on > 0) { separator = ""; if (set_changes > 0) { offset += OS::SNPrintF(buffer + offset, ", "); } if (positive_depends_on) { offset += OS::SNPrintF(buffer + offset, "depends on ["); } else { offset += OS::SNPrintF(buffer + offset, "depends on all except ["); } for (int bit = 0; bit < kLastFlag; ++bit) { if (((flags.ToIntegral() & (1 << bit)) != 0) == positive_depends_on) { switch (static_cast<GVNFlag>(bit)) { #define DECLARE_FLAG(type) \ case kDependsOn##type: \ offset += OS::SNPrintF(buffer + offset, separator); \ offset += OS::SNPrintF(buffer + offset, #type); \ separator = comma; \ break; GVN_TRACKED_FLAG_LIST(DECLARE_FLAG) GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG) #undef DECLARE_FLAG default: break; } } } offset += OS::SNPrintF(buffer + offset, "]"); } #else OS::SNPrintF(buffer, "0x%08X", flags.ToIntegral()); #endif size_t string_len = strlen(underlying_buffer) + 1; ASSERT(string_len <= sizeof(underlying_buffer)); char* result = new char[strlen(underlying_buffer) + 1]; OS::MemCopy(result, underlying_buffer, string_len); return SmartArrayPointer<char>(result); } void HGlobalValueNumberingPhase::LoopInvariantCodeMotion() { TRACE_GVN_1("Using optimistic loop invariant code motion: %s\n", graph()->use_optimistic_licm() ? "yes" : "no"); for (int i = graph()->blocks()->length() - 1; i >= 0; --i) { HBasicBlock* block = graph()->blocks()->at(i); if (block->IsLoopHeader()) { GVNFlagSet side_effects = loop_side_effects_[block->block_id()]; TRACE_GVN_2("Try loop invariant motion for block B%d %s\n", block->block_id(), *GetGVNFlagsString(side_effects)); GVNFlagSet accumulated_first_time_depends; GVNFlagSet accumulated_first_time_changes; HBasicBlock* last = block->loop_information()->GetLastBackEdge(); for (int j = block->block_id(); j <= last->block_id(); ++j) { ProcessLoopBlock(graph()->blocks()->at(j), block, side_effects, &accumulated_first_time_depends, &accumulated_first_time_changes); } } } } void HGlobalValueNumberingPhase::ProcessLoopBlock( HBasicBlock* block, HBasicBlock* loop_header, GVNFlagSet loop_kills, GVNFlagSet* first_time_depends, GVNFlagSet* first_time_changes) { HBasicBlock* pre_header = loop_header->predecessors()->at(0); GVNFlagSet depends_flags = HValue::ConvertChangesToDependsFlags(loop_kills); TRACE_GVN_2("Loop invariant motion for B%d %s\n", block->block_id(), *GetGVNFlagsString(depends_flags)); HInstruction* instr = block->first(); while (instr != NULL) { HInstruction* next = instr->next(); bool hoisted = false; if (instr->CheckFlag(HValue::kUseGVN)) { TRACE_GVN_4("Checking instruction %d (%s) %s. Loop %s\n", instr->id(), instr->Mnemonic(), *GetGVNFlagsString(instr->gvn_flags()), *GetGVNFlagsString(loop_kills)); bool can_hoist = !instr->gvn_flags().ContainsAnyOf(depends_flags); if (can_hoist && !graph()->use_optimistic_licm()) { can_hoist = block->IsLoopSuccessorDominator(); } if (can_hoist) { bool inputs_loop_invariant = true; for (int i = 0; i < instr->OperandCount(); ++i) { if (instr->OperandAt(i)->IsDefinedAfter(pre_header)) { inputs_loop_invariant = false; } } if (inputs_loop_invariant && ShouldMove(instr, loop_header)) { TRACE_GVN_1("Hoisting loop invariant instruction %d\n", instr->id()); // Move the instruction out of the loop. instr->Unlink(); instr->InsertBefore(pre_header->end()); if (instr->HasSideEffects()) removed_side_effects_ = true; hoisted = true; } } } if (!hoisted) { // If an instruction is not hoisted, we have to account for its side // effects when hoisting later HTransitionElementsKind instructions. GVNFlagSet previous_depends = *first_time_depends; GVNFlagSet previous_changes = *first_time_changes; first_time_depends->Add(instr->DependsOnFlags()); first_time_changes->Add(instr->ChangesFlags()); if (!(previous_depends == *first_time_depends)) { TRACE_GVN_1("Updated first-time accumulated %s\n", *GetGVNFlagsString(*first_time_depends)); } if (!(previous_changes == *first_time_changes)) { TRACE_GVN_1("Updated first-time accumulated %s\n", *GetGVNFlagsString(*first_time_changes)); } } instr = next; } } bool HGlobalValueNumberingPhase::AllowCodeMotion() { return info()->IsStub() || info()->opt_count() + 1 < FLAG_max_opt_count; } bool HGlobalValueNumberingPhase::ShouldMove(HInstruction* instr, HBasicBlock* loop_header) { // If we've disabled code motion or we're in a block that unconditionally // deoptimizes, don't move any instructions. return AllowCodeMotion() && !instr->block()->IsDeoptimizing() && instr->block()->IsReachable(); } GVNFlagSet HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock( HBasicBlock* dominator, HBasicBlock* dominated) { GVNFlagSet side_effects; for (int i = 0; i < dominated->predecessors()->length(); ++i) { HBasicBlock* block = dominated->predecessors()->at(i); if (dominator->block_id() < block->block_id() && block->block_id() < dominated->block_id() && !visited_on_paths_.Contains(block->block_id())) { visited_on_paths_.Add(block->block_id()); side_effects.Add(block_side_effects_[block->block_id()]); if (block->IsLoopHeader()) { side_effects.Add(loop_side_effects_[block->block_id()]); } side_effects.Add(CollectSideEffectsOnPathsToDominatedBlock( dominator, block)); } } return side_effects; } // Each instance of this class is like a "stack frame" for the recursive // traversal of the dominator tree done during GVN (the stack is handled // as a double linked list). // We reuse frames when possible so the list length is limited by the depth // of the dominator tree but this forces us to initialize each frame calling // an explicit "Initialize" method instead of a using constructor. class GvnBasicBlockState: public ZoneObject { public: static GvnBasicBlockState* CreateEntry(Zone* zone, HBasicBlock* entry_block, HValueMap* entry_map) { return new(zone) GvnBasicBlockState(NULL, entry_block, entry_map, NULL, zone); } HBasicBlock* block() { return block_; } HValueMap* map() { return map_; } HSideEffectMap* dominators() { return &dominators_; } GvnBasicBlockState* next_in_dominator_tree_traversal( Zone* zone, HBasicBlock** dominator) { // This assignment needs to happen before calling next_dominated() because // that call can reuse "this" if we are at the last dominated block. *dominator = block(); GvnBasicBlockState* result = next_dominated(zone); if (result == NULL) { GvnBasicBlockState* dominator_state = pop(); if (dominator_state != NULL) { // This branch is guaranteed not to return NULL because pop() never // returns a state where "is_done() == true". *dominator = dominator_state->block(); result = dominator_state->next_dominated(zone); } else { // Unnecessary (we are returning NULL) but done for cleanness. *dominator = NULL; } } return result; } private: void Initialize(HBasicBlock* block, HValueMap* map, HSideEffectMap* dominators, bool copy_map, Zone* zone) { block_ = block; map_ = copy_map ? map->Copy(zone) : map; dominated_index_ = -1; length_ = block->dominated_blocks()->length(); if (dominators != NULL) { dominators_ = *dominators; } } bool is_done() { return dominated_index_ >= length_; } GvnBasicBlockState(GvnBasicBlockState* previous, HBasicBlock* block, HValueMap* map, HSideEffectMap* dominators, Zone* zone) : previous_(previous), next_(NULL) { Initialize(block, map, dominators, true, zone); } GvnBasicBlockState* next_dominated(Zone* zone) { dominated_index_++; if (dominated_index_ == length_ - 1) { // No need to copy the map for the last child in the dominator tree. Initialize(block_->dominated_blocks()->at(dominated_index_), map(), dominators(), false, zone); return this; } else if (dominated_index_ < length_) { return push(zone, block_->dominated_blocks()->at(dominated_index_)); } else { return NULL; } } GvnBasicBlockState* push(Zone* zone, HBasicBlock* block) { if (next_ == NULL) { next_ = new(zone) GvnBasicBlockState(this, block, map(), dominators(), zone); } else { next_->Initialize(block, map(), dominators(), true, zone); } return next_; } GvnBasicBlockState* pop() { GvnBasicBlockState* result = previous_; while (result != NULL && result->is_done()) { TRACE_GVN_2("Backtracking from block B%d to block b%d\n", block()->block_id(), previous_->block()->block_id()) result = result->previous_; } return result; } GvnBasicBlockState* previous_; GvnBasicBlockState* next_; HBasicBlock* block_; HValueMap* map_; HSideEffectMap dominators_; int dominated_index_; int length_; }; // This is a recursive traversal of the dominator tree but it has been turned // into a loop to avoid stack overflows. // The logical "stack frames" of the recursion are kept in a list of // GvnBasicBlockState instances. void HGlobalValueNumberingPhase::AnalyzeGraph() { HBasicBlock* entry_block = graph()->entry_block(); HValueMap* entry_map = new(zone()) HValueMap(zone()); GvnBasicBlockState* current = GvnBasicBlockState::CreateEntry(zone(), entry_block, entry_map); while (current != NULL) { HBasicBlock* block = current->block(); HValueMap* map = current->map(); HSideEffectMap* dominators = current->dominators(); TRACE_GVN_2("Analyzing block B%d%s\n", block->block_id(), block->IsLoopHeader() ? " (loop header)" : ""); // If this is a loop header kill everything killed by the loop. if (block->IsLoopHeader()) { map->Kill(loop_side_effects_[block->block_id()]); dominators->Kill(loop_side_effects_[block->block_id()]); } // Go through all instructions of the current block. for (HInstructionIterator it(block); !it.Done(); it.Advance()) { HInstruction* instr = it.Current(); if (instr->CheckFlag(HValue::kTrackSideEffectDominators)) { for (int i = 0; i < kNumberOfTrackedSideEffects; i++) { HValue* other = dominators->at(i); GVNFlag changes_flag = HValue::ChangesFlagFromInt(i); GVNFlag depends_on_flag = HValue::DependsOnFlagFromInt(i); if (instr->DependsOnFlags().Contains(depends_on_flag) && (other != NULL)) { TRACE_GVN_5("Side-effect #%d in %d (%s) is dominated by %d (%s)\n", i, instr->id(), instr->Mnemonic(), other->id(), other->Mnemonic()); instr->HandleSideEffectDominator(changes_flag, other); } } } // Instruction was unlinked during graph traversal. if (!instr->IsLinked()) continue; GVNFlagSet flags = instr->ChangesFlags(); if (!flags.IsEmpty()) { // Clear all instructions in the map that are affected by side effects. // Store instruction as the dominating one for tracked side effects. map->Kill(flags); dominators->Store(flags, instr); TRACE_GVN_2("Instruction %d %s\n", instr->id(), *GetGVNFlagsString(flags)); } if (instr->CheckFlag(HValue::kUseGVN)) { ASSERT(!instr->HasObservableSideEffects()); HValue* other = map->Lookup(instr); if (other != NULL) { ASSERT(instr->Equals(other) && other->Equals(instr)); TRACE_GVN_4("Replacing value %d (%s) with value %d (%s)\n", instr->id(), instr->Mnemonic(), other->id(), other->Mnemonic()); if (instr->HasSideEffects()) removed_side_effects_ = true; instr->DeleteAndReplaceWith(other); } else { map->Add(instr, zone()); } } } HBasicBlock* dominator_block; GvnBasicBlockState* next = current->next_in_dominator_tree_traversal(zone(), &dominator_block); if (next != NULL) { HBasicBlock* dominated = next->block(); HValueMap* successor_map = next->map(); HSideEffectMap* successor_dominators = next->dominators(); // Kill everything killed on any path between this block and the // dominated block. We don't have to traverse these paths if the // value map and the dominators list is already empty. If the range // of block ids (block_id, dominated_id) is empty there are no such // paths. if ((!successor_map->IsEmpty() || !successor_dominators->IsEmpty()) && dominator_block->block_id() + 1 < dominated->block_id()) { visited_on_paths_.Clear(); GVNFlagSet side_effects_on_all_paths = CollectSideEffectsOnPathsToDominatedBlock(dominator_block, dominated); successor_map->Kill(side_effects_on_all_paths); successor_dominators->Kill(side_effects_on_all_paths); } } current = next; } } } } // namespace v8::internal