// 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"
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "src/hydrogen.h"
+#include "src/hydrogen-gvn.h"
+#include "src/v8.h"
namespace v8 {
namespace internal {
-class HValueMap: public ZoneObject {
+class HInstructionMap V8_FINAL : public ZoneObject {
public:
- explicit HValueMap(Zone* zone)
+ HInstructionMap(Zone* zone, SideEffectsTracker* side_effects_tracker)
: array_size_(0),
lists_size_(0),
count_(0),
- present_flags_(0),
array_(NULL),
lists_(NULL),
- free_list_head_(kNil) {
+ free_list_head_(kNil),
+ side_effects_tracker_(side_effects_tracker) {
ResizeLists(kInitialSize, zone);
Resize(kInitialSize, zone);
}
- void Kill(GVNFlagSet flags);
+ void Kill(SideEffects side_effects);
- void Add(HValue* value, Zone* zone) {
- present_flags_.Add(value->gvn_flags());
- Insert(value, zone);
+ void Add(HInstruction* instr, Zone* zone) {
+ present_depends_on_.Add(side_effects_tracker_->ComputeDependsOn(instr));
+ Insert(instr, zone);
}
- HValue* Lookup(HValue* value) const;
+ HInstruction* Lookup(HInstruction* instr) const;
- HValueMap* Copy(Zone* zone) const {
- return new(zone) HValueMap(zone, this);
+ HInstructionMap* Copy(Zone* zone) const {
+ return new(zone) HInstructionMap(zone, this);
}
bool IsEmpty() const { return count_ == 0; }
private:
- // A linked list of HValue* values. Stored in arrays.
- struct HValueMapListElement {
- HValue* value;
+ // A linked list of HInstruction* values. Stored in arrays.
+ struct HInstructionMapListElement {
+ HInstruction* instr;
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);
+ HInstructionMap(Zone* zone, const HInstructionMap* other);
void Resize(int new_size, Zone* zone);
void ResizeLists(int new_size, Zone* zone);
- void Insert(HValue* value, Zone* zone);
+ void Insert(HInstruction* instr, 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
+ int count_; // The number of values stored in the HInstructionMap.
+ SideEffects present_depends_on_;
+ HInstructionMapListElement* 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.
+ HInstructionMapListElement* lists_;
+ // The linked lists containing hash collisions.
int free_list_head_; // Unused elements in lists_ are on the free list.
+ SideEffectsTracker* side_effects_tracker_;
};
-class HSideEffectMap BASE_EMBEDDED {
+class HSideEffectMap V8_FINAL BASE_EMBEDDED {
public:
HSideEffectMap();
explicit HSideEffectMap(HSideEffectMap* other);
HSideEffectMap& operator= (const HSideEffectMap& other);
- void Kill(GVNFlagSet flags);
+ void Kill(SideEffects side_effects);
- void Store(GVNFlagSet flags, HInstruction* instr);
+ void Store(SideEffects side_effects, HInstruction* instr);
bool IsEmpty() const { return count_ == 0; }
inline HInstruction* operator[](int i) const {
- ASSERT(0 <= i);
- ASSERT(i < kNumberOfTrackedSideEffects);
+ DCHECK(0 <= i);
+ DCHECK(i < kNumberOfTrackedSideEffects);
return data_[i];
}
inline HInstruction* at(int i) const { return operator[](i); }
void TraceGVN(const char* msg, ...) {
va_list arguments;
va_start(arguments, msg);
- OS::VPrint(msg, arguments);
+ base::OS::VPrint(msg, arguments);
va_end(arguments);
}
}
-HValueMap::HValueMap(Zone* zone, const HValueMap* other)
+HInstructionMap::HInstructionMap(Zone* zone, const HInstructionMap* 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));
+ present_depends_on_(other->present_depends_on_),
+ array_(zone->NewArray<HInstructionMapListElement>(other->array_size_)),
+ lists_(zone->NewArray<HInstructionMapListElement>(other->lists_size_)),
+ free_list_head_(other->free_list_head_),
+ side_effects_tracker_(other->side_effects_tracker_) {
+ MemCopy(array_, other->array_,
+ array_size_ * sizeof(HInstructionMapListElement));
+ MemCopy(lists_, other->lists_,
+ lists_size_ * sizeof(HInstructionMapListElement));
}
-void HValueMap::Kill(GVNFlagSet flags) {
- GVNFlagSet depends_flags = HValue::ConvertChangesToDependsFlags(flags);
- if (!present_flags_.ContainsAnyOf(depends_flags)) return;
- present_flags_.RemoveAll();
+void HInstructionMap::Kill(SideEffects changes) {
+ if (!present_depends_on_.ContainsAnyOf(changes)) return;
+ present_depends_on_.RemoveAll();
for (int i = 0; i < array_size_; ++i) {
- HValue* value = array_[i].value;
- if (value != NULL) {
+ HInstruction* instr = array_[i].instr;
+ if (instr != 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)) {
+ HInstruction* instr = lists_[current].instr;
+ SideEffects depends_on = side_effects_tracker_->ComputeDependsOn(instr);
+ if (depends_on.ContainsAnyOf(changes)) {
// Drop it.
count_--;
lists_[current].next = free_list_head_;
// Keep it.
lists_[current].next = kept;
kept = current;
- present_flags_.Add(value->gvn_flags());
+ present_depends_on_.Add(depends_on);
}
}
array_[i].next = kept;
// Now possibly drop directly indexed element.
- value = array_[i].value;
- if (value->gvn_flags().ContainsAnyOf(depends_flags)) { // Drop it.
+ instr = array_[i].instr;
+ SideEffects depends_on = side_effects_tracker_->ComputeDependsOn(instr);
+ if (depends_on.ContainsAnyOf(changes)) { // Drop it.
count_--;
int head = array_[i].next;
if (head == kNil) {
- array_[i].value = NULL;
+ array_[i].instr = NULL;
} else {
- array_[i].value = lists_[head].value;
+ array_[i].instr = lists_[head].instr;
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.
+ present_depends_on_.Add(depends_on); // Keep it.
}
}
}
}
-HValue* HValueMap::Lookup(HValue* value) const {
- uint32_t hash = static_cast<uint32_t>(value->Hashcode());
+HInstruction* HInstructionMap::Lookup(HInstruction* instr) const {
+ uint32_t hash = static_cast<uint32_t>(instr->Hashcode());
uint32_t pos = Bound(hash);
- if (array_[pos].value != NULL) {
- if (array_[pos].value->Equals(value)) return array_[pos].value;
+ if (array_[pos].instr != NULL) {
+ if (array_[pos].instr->Equals(instr)) return array_[pos].instr;
int next = array_[pos].next;
while (next != kNil) {
- if (lists_[next].value->Equals(value)) return lists_[next].value;
+ if (lists_[next].instr->Equals(instr)) return lists_[next].instr;
next = lists_[next].next;
}
}
}
-void HValueMap::Resize(int new_size, Zone* zone) {
- ASSERT(new_size > count_);
+void HInstructionMap::Resize(int new_size, Zone* zone) {
+ DCHECK(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.
ResizeLists(lists_size_ << 1, zone);
}
- HValueMapListElement* new_array =
- zone->NewArray<HValueMapListElement>(new_size);
- memset(new_array, 0, sizeof(HValueMapListElement) * new_size);
+ HInstructionMapListElement* new_array =
+ zone->NewArray<HInstructionMapListElement>(new_size);
+ memset(new_array, 0, sizeof(HInstructionMapListElement) * new_size);
- HValueMapListElement* old_array = array_;
+ HInstructionMapListElement* old_array = array_;
int old_size = array_size_;
int old_count = count_;
count_ = 0;
- // Do not modify present_flags_. It is currently correct.
+ // Do not modify present_depends_on_. 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) {
+ if (old_array[i].instr != NULL) {
int current = old_array[i].next;
while (current != kNil) {
- Insert(lists_[current].value, zone);
+ Insert(lists_[current].instr, 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);
+ // Rehash the directly stored instruction.
+ Insert(old_array[i].instr, zone);
}
}
}
USE(old_count);
- ASSERT(count_ == old_count);
+ DCHECK(count_ == old_count);
}
-void HValueMap::ResizeLists(int new_size, Zone* zone) {
- ASSERT(new_size > lists_size_);
+void HInstructionMap::ResizeLists(int new_size, Zone* zone) {
+ DCHECK(new_size > lists_size_);
- HValueMapListElement* new_lists =
- zone->NewArray<HValueMapListElement>(new_size);
- memset(new_lists, 0, sizeof(HValueMapListElement) * new_size);
+ HInstructionMapListElement* new_lists =
+ zone->NewArray<HInstructionMapListElement>(new_size);
+ memset(new_lists, 0, sizeof(HInstructionMapListElement) * new_size);
- HValueMapListElement* old_lists = lists_;
+ HInstructionMapListElement* 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));
+ MemCopy(lists_, old_lists, old_size * sizeof(HInstructionMapListElement));
}
for (int i = old_size; i < lists_size_; ++i) {
lists_[i].next = free_list_head_;
}
-void HValueMap::Insert(HValue* value, Zone* zone) {
- ASSERT(value != NULL);
+void HInstructionMap::Insert(HInstruction* instr, Zone* zone) {
+ DCHECK(instr != NULL);
// Resizing when half of the hashtable is filled up.
if (count_ >= array_size_ >> 1) Resize(array_size_ << 1, zone);
- ASSERT(count_ < array_size_);
+ DCHECK(count_ < array_size_);
count_++;
- uint32_t pos = Bound(static_cast<uint32_t>(value->Hashcode()));
- if (array_[pos].value == NULL) {
- array_[pos].value = value;
+ uint32_t pos = Bound(static_cast<uint32_t>(instr->Hashcode()));
+ if (array_[pos].instr == NULL) {
+ array_[pos].instr = instr;
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);
+ DCHECK(new_element_pos != kNil);
free_list_head_ = lists_[free_list_head_].next;
- lists_[new_element_pos].value = value;
+ lists_[new_element_pos].instr = instr;
lists_[new_element_pos].next = array_[pos].next;
- ASSERT(array_[pos].next == kNil || lists_[array_[pos].next].value != NULL);
+ DCHECK(array_[pos].next == kNil || lists_[array_[pos].next].instr != NULL);
array_[pos].next = new_element_pos;
}
}
}
-HSideEffectMap& HSideEffectMap::operator= (const HSideEffectMap& other) {
+HSideEffectMap& HSideEffectMap::operator=(const HSideEffectMap& other) {
if (this != &other) {
- OS::MemCopy(data_, other.data_, kNumberOfTrackedSideEffects * kPointerSize);
+ MemCopy(data_, other.data_, kNumberOfTrackedSideEffects * kPointerSize);
}
return *this;
}
-void HSideEffectMap::Kill(GVNFlagSet flags) {
+void HSideEffectMap::Kill(SideEffects side_effects) {
for (int i = 0; i < kNumberOfTrackedSideEffects; i++) {
- GVNFlag changes_flag = HValue::ChangesFlagFromInt(i);
- if (flags.Contains(changes_flag)) {
+ if (side_effects.ContainsFlag(GVNFlagFromInt(i))) {
if (data_[i] != NULL) count_--;
data_[i] = NULL;
}
}
-void HSideEffectMap::Store(GVNFlagSet flags, HInstruction* instr) {
+void HSideEffectMap::Store(SideEffects side_effects, HInstruction* instr) {
for (int i = 0; i < kNumberOfTrackedSideEffects; i++) {
- GVNFlag changes_flag = HValue::ChangesFlagFromInt(i);
- if (flags.Contains(changes_flag)) {
+ if (side_effects.ContainsFlag(GVNFlagFromInt(i))) {
if (data_[i] == NULL) count_++;
data_[i] = instr;
}
}
+SideEffects SideEffectsTracker::ComputeChanges(HInstruction* instr) {
+ int index;
+ SideEffects result(instr->ChangesFlags());
+ if (result.ContainsFlag(kGlobalVars)) {
+ if (instr->IsStoreGlobalCell() &&
+ ComputeGlobalVar(HStoreGlobalCell::cast(instr)->cell(), &index)) {
+ result.RemoveFlag(kGlobalVars);
+ result.AddSpecial(GlobalVar(index));
+ } else {
+ for (index = 0; index < kNumberOfGlobalVars; ++index) {
+ result.AddSpecial(GlobalVar(index));
+ }
+ }
+ }
+ if (result.ContainsFlag(kInobjectFields)) {
+ if (instr->IsStoreNamedField() &&
+ ComputeInobjectField(HStoreNamedField::cast(instr)->access(), &index)) {
+ result.RemoveFlag(kInobjectFields);
+ result.AddSpecial(InobjectField(index));
+ } else {
+ for (index = 0; index < kNumberOfInobjectFields; ++index) {
+ result.AddSpecial(InobjectField(index));
+ }
+ }
+ }
+ return result;
+}
+
+
+SideEffects SideEffectsTracker::ComputeDependsOn(HInstruction* instr) {
+ int index;
+ SideEffects result(instr->DependsOnFlags());
+ if (result.ContainsFlag(kGlobalVars)) {
+ if (instr->IsLoadGlobalCell() &&
+ ComputeGlobalVar(HLoadGlobalCell::cast(instr)->cell(), &index)) {
+ result.RemoveFlag(kGlobalVars);
+ result.AddSpecial(GlobalVar(index));
+ } else {
+ for (index = 0; index < kNumberOfGlobalVars; ++index) {
+ result.AddSpecial(GlobalVar(index));
+ }
+ }
+ }
+ if (result.ContainsFlag(kInobjectFields)) {
+ if (instr->IsLoadNamedField() &&
+ ComputeInobjectField(HLoadNamedField::cast(instr)->access(), &index)) {
+ result.RemoveFlag(kInobjectFields);
+ result.AddSpecial(InobjectField(index));
+ } else {
+ for (index = 0; index < kNumberOfInobjectFields; ++index) {
+ result.AddSpecial(InobjectField(index));
+ }
+ }
+ }
+ return result;
+}
+
+
+OStream& operator<<(OStream& os, const TrackedEffects& te) {
+ SideEffectsTracker* t = te.tracker;
+ const char* separator = "";
+ os << "[";
+ for (int bit = 0; bit < kNumberOfFlags; ++bit) {
+ GVNFlag flag = GVNFlagFromInt(bit);
+ if (te.effects.ContainsFlag(flag)) {
+ os << separator;
+ separator = ", ";
+ switch (flag) {
+#define DECLARE_FLAG(Type) \
+ case k##Type: \
+ os << #Type; \
+ break;
+GVN_TRACKED_FLAG_LIST(DECLARE_FLAG)
+GVN_UNTRACKED_FLAG_LIST(DECLARE_FLAG)
+#undef DECLARE_FLAG
+ default:
+ break;
+ }
+ }
+ }
+ for (int index = 0; index < t->num_global_vars_; ++index) {
+ if (te.effects.ContainsSpecial(t->GlobalVar(index))) {
+ os << separator << "[" << *t->global_vars_[index].handle() << "]";
+ separator = ", ";
+ }
+ }
+ for (int index = 0; index < t->num_inobject_fields_; ++index) {
+ if (te.effects.ContainsSpecial(t->InobjectField(index))) {
+ os << separator << t->inobject_fields_[index];
+ separator = ", ";
+ }
+ }
+ os << "]";
+ return os;
+}
+
+
+bool SideEffectsTracker::ComputeGlobalVar(Unique<Cell> cell, int* index) {
+ for (int i = 0; i < num_global_vars_; ++i) {
+ if (cell == global_vars_[i]) {
+ *index = i;
+ return true;
+ }
+ }
+ if (num_global_vars_ < kNumberOfGlobalVars) {
+ if (FLAG_trace_gvn) {
+ OFStream os(stdout);
+ os << "Tracking global var [" << *cell.handle() << "] "
+ << "(mapped to index " << num_global_vars_ << ")" << endl;
+ }
+ *index = num_global_vars_;
+ global_vars_[num_global_vars_++] = cell;
+ return true;
+ }
+ return false;
+}
+
+
+bool SideEffectsTracker::ComputeInobjectField(HObjectAccess access,
+ int* index) {
+ for (int i = 0; i < num_inobject_fields_; ++i) {
+ if (access.Equals(inobject_fields_[i])) {
+ *index = i;
+ return true;
+ }
+ }
+ if (num_inobject_fields_ < kNumberOfInobjectFields) {
+ if (FLAG_trace_gvn) {
+ OFStream os(stdout);
+ os << "Tracking inobject field access " << access << " (mapped to index "
+ << num_inobject_fields_ << ")" << endl;
+ }
+ *index = num_inobject_fields_;
+ inobject_fields_[num_inobject_fields_++] = access;
+ return true;
+ }
+ return false;
+}
+
+
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();
+ : 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()) {
+ DCHECK(!AllowHandleAllocation::IsAllowed());
+ block_side_effects_.AddBlock(
+ SideEffects(), graph->blocks()->length(), zone());
+ loop_side_effects_.AddBlock(
+ SideEffects(), graph->blocks()->length(), zone());
}
-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();
+void HGlobalValueNumberingPhase::Run() {
+ DCHECK(!removed_side_effects_);
+ for (int i = FLAG_gvn_iterations; i > 0; --i) {
+ // Compute the side effects.
+ ComputeBlockSideEffects();
+
+ // Perform loop invariant code motion if requested.
+ if (FLAG_loop_invariant_code_motion) LoopInvariantCodeMotion();
+
+ // Perform the actual value numbering.
+ AnalyzeGraph();
+
+ // Continue GVN if we removed any side effects.
+ if (!removed_side_effects_) break;
+ removed_side_effects_ = false;
+
+ // Clear all side effects.
+ DCHECK_EQ(block_side_effects_.length(), graph()->blocks()->length());
+ DCHECK_EQ(loop_side_effects_.length(), graph()->blocks()->length());
+ for (int i = 0; i < graph()->blocks()->length(); ++i) {
+ block_side_effects_[i].RemoveAll();
+ loop_side_effects_[i].RemoveAll();
+ }
+ visited_on_paths_.Clear();
}
+}
+
+
+void HGlobalValueNumberingPhase::ComputeBlockSideEffects() {
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;
+ SideEffects 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());
+ side_effects.Add(side_effects_tracker_.ComputeChanges(instr));
}
block_side_effects_[id].Add(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.Contains(static_cast<GVNFlag>(bit))) {
- 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.Contains(static_cast<GVNFlag>(bit)) == 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.Contains(static_cast<GVNFlag>(bit)) == 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).get());
-
- GVNFlagSet accumulated_first_time_depends;
- GVNFlagSet accumulated_first_time_changes;
+ SideEffects side_effects = loop_side_effects_[block->block_id()];
+ if (FLAG_trace_gvn) {
+ OFStream os(stdout);
+ os << "Try loop invariant motion for " << *block << " changes "
+ << Print(side_effects) << endl;
+ }
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);
+ ProcessLoopBlock(graph()->blocks()->at(j), block, side_effects);
}
}
}
void HGlobalValueNumberingPhase::ProcessLoopBlock(
HBasicBlock* block,
HBasicBlock* loop_header,
- GVNFlagSet loop_kills,
- GVNFlagSet* first_time_depends,
- GVNFlagSet* first_time_changes) {
+ SideEffects loop_kills) {
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).get());
+ if (FLAG_trace_gvn) {
+ OFStream os(stdout);
+ os << "Loop invariant code motion for " << *block << " depends on "
+ << Print(loop_kills) << endl;
+ }
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()).get(),
- GetGVNFlagsString(loop_kills).get());
- bool can_hoist = !instr->gvn_flags().ContainsAnyOf(depends_flags);
+ SideEffects changes = side_effects_tracker_.ComputeChanges(instr);
+ SideEffects depends_on = side_effects_tracker_.ComputeDependsOn(instr);
+ if (FLAG_trace_gvn) {
+ OFStream os(stdout);
+ os << "Checking instruction i" << instr->id() << " ("
+ << instr->Mnemonic() << ") changes " << Print(changes)
+ << ", depends on " << Print(depends_on) << ". Loop changes "
+ << Print(loop_kills) << endl;
+ }
+ bool can_hoist = !depends_on.ContainsAnyOf(loop_kills);
if (can_hoist && !graph()->use_optimistic_licm()) {
can_hoist = block->IsLoopSuccessorDominator();
}
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).get());
- }
- if (!(previous_changes == *first_time_changes)) {
- TRACE_GVN_1("Updated first-time accumulated %s\n",
- GetGVNFlagsString(*first_time_changes).get());
- }
- }
instr = next;
}
}
}
-GVNFlagSet
+SideEffects
HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock(
HBasicBlock* dominator, HBasicBlock* dominated) {
- GVNFlagSet side_effects;
+ SideEffects side_effects;
for (int i = 0; i < dominated->predecessors()->length(); ++i) {
HBasicBlock* block = dominated->predecessors()->at(i);
if (dominator->block_id() < block->block_id() &&
public:
static GvnBasicBlockState* CreateEntry(Zone* zone,
HBasicBlock* entry_block,
- HValueMap* entry_map) {
+ HInstructionMap* entry_map) {
return new(zone)
GvnBasicBlockState(NULL, entry_block, entry_map, NULL, zone);
}
HBasicBlock* block() { return block_; }
- HValueMap* map() { return map_; }
+ HInstructionMap* map() { return map_; }
HSideEffectMap* dominators() { return &dominators_; }
GvnBasicBlockState* next_in_dominator_tree_traversal(
private:
void Initialize(HBasicBlock* block,
- HValueMap* map,
+ HInstructionMap* map,
HSideEffectMap* dominators,
bool copy_map,
Zone* zone) {
GvnBasicBlockState(GvnBasicBlockState* previous,
HBasicBlock* block,
- HValueMap* map,
+ HInstructionMap* map,
HSideEffectMap* dominators,
Zone* zone)
: previous_(previous), next_(NULL) {
GvnBasicBlockState* previous_;
GvnBasicBlockState* next_;
HBasicBlock* block_;
- HValueMap* map_;
+ HInstructionMap* map_;
HSideEffectMap dominators_;
int dominated_index_;
int length_;
// GvnBasicBlockState instances.
void HGlobalValueNumberingPhase::AnalyzeGraph() {
HBasicBlock* entry_block = graph()->entry_block();
- HValueMap* entry_map = new(zone()) HValueMap(zone());
+ HInstructionMap* entry_map =
+ new(zone()) HInstructionMap(zone(), &side_effects_tracker_);
GvnBasicBlockState* current =
GvnBasicBlockState::CreateEntry(zone(), entry_block, entry_map);
while (current != NULL) {
HBasicBlock* block = current->block();
- HValueMap* map = current->map();
+ HInstructionMap* map = current->map();
HSideEffectMap* dominators = current->dominators();
TRACE_GVN_2("Analyzing block B%d%s\n",
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)) {
+ GVNFlag flag = GVNFlagFromInt(i);
+ if (instr->DependsOnFlags().Contains(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);
+ if (instr->HandleSideEffectDominator(flag, other)) {
+ removed_side_effects_ = true;
+ }
}
}
}
// Instruction was unlinked during graph traversal.
if (!instr->IsLinked()) continue;
- GVNFlagSet flags = instr->ChangesFlags();
- if (!flags.IsEmpty()) {
+ SideEffects changes = side_effects_tracker_.ComputeChanges(instr);
+ if (!changes.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).get());
+ map->Kill(changes);
+ dominators->Store(changes, instr);
+ if (FLAG_trace_gvn) {
+ OFStream os(stdout);
+ os << "Instruction i" << instr->id() << " changes " << Print(changes)
+ << endl;
+ }
}
- if (instr->CheckFlag(HValue::kUseGVN)) {
- ASSERT(!instr->HasObservableSideEffects());
- HValue* other = map->Lookup(instr);
+ if (instr->CheckFlag(HValue::kUseGVN) &&
+ !instr->CheckFlag(HValue::kCantBeReplaced)) {
+ DCHECK(!instr->HasObservableSideEffects());
+ HInstruction* 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",
+ DCHECK(instr->Equals(other) && other->Equals(instr));
+ TRACE_GVN_4("Replacing instruction i%d (%s) with i%d (%s)\n",
instr->id(),
instr->Mnemonic(),
other->id(),
if (next != NULL) {
HBasicBlock* dominated = next->block();
- HValueMap* successor_map = next->map();
+ HInstructionMap* successor_map = next->map();
HSideEffectMap* successor_dominators = next->dominators();
// Kill everything killed on any path between this block and the
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 =
+ SideEffects side_effects_on_all_paths =
CollectSideEffectsOnPathsToDominatedBlock(dominator_block,
dominated);
successor_map->Kill(side_effects_on_all_paths);
projects / platform / framework / web / crosswalk.git / blobdiff