Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(369)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/hydrogen.cc

Issue 6690006: Improve GVN dependency tracking by adding parameters to certain flags.
Patch Set: Created 9 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/hydrogen.h ('k') | src/hydrogen-instructions.h » ('j') | src/hydrogen-instructions.h » ('J')
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/hydrogen.cc
diff --git a/src/hydrogen.cc b/src/hydrogen.cc
index 25a6db3ac178c12cf2b32f1351dc008502e7bb6f..bfcdfd9e300bb3a20fd237eb08b808fab83bf86a 100644
--- a/src/hydrogen.cc
+++ b/src/hydrogen.cc
@@ -1005,6 +1005,129 @@ void TraceGVN(const char* msg, ...) {
}
}
+class HEffectSet: public ZoneObject {
+ public:
+ HEffectSet() : parameters_(0) {
fschneider 2011/03/16 15:43:28 Since Initialize() also initializes paramters_, th
+ Initialize();
+ }
+
+ explicit HEffectSet(int flags) : parameters_(0) {
fschneider 2011/03/16 15:43:28 Same here.
+ Initialize();
+ AddFlags(flags);
+ }
+
+ void Initialize() {
+ flags_ = 0;
+ flags_without_parameters_ = 0;
+ parameters_.Initialize(0);
+ }
+
+ void Add(HValue* value) {
+ int flags = value->flags() & HValue::ChangesFlagsMask();
+ if (flags == 0) return;
+ if (value->CheckFlag(HValue::kHasGVNParameter)) {
+ AddWithParameter(flags, value->GetGVNParameter());
+ } else {
+ AddWithoutParameter(flags);
+ }
+ }
+
+ void AddAll(const HEffectSet& other) {
+ flags_ |= other.flags_;
+ flags_without_parameters_ |= other.flags_without_parameters_;
+ for (int i = 0; i < other.parameters_.length(); i++) {
+ int flag = i << 1;
fschneider 2011/03/16 15:43:28 You could move this line to after the continue.
+ if (other.parameters_[i] == NULL) continue;
+ for (int j = 0; j < other.parameters_[i]->length(); j++) {
+ InternalAddWithParameter(flag, other.parameters_[i]->at(j));
+ }
+ }
+ }
+
+ bool HasEffectOnAny(int depends_flags) const {
+ return (HValue::ConvertDependsToChangesFlags(depends_flags) & flags_) != 0;
+ }
+
+ bool HasEffectOn(HValue* value) const {
+ ASSERT(value->CheckFlag(HValue::kUseGVN));
+ int affected_flags =
+ HValue::ConvertDependsToChangesFlags(value->flags()) & flags_;
+ if (affected_flags == 0) return false;
+ if (!value->CheckFlag(HValue::kHasGVNParameter)) return true;
+ if ((affected_flags & flags_without_parameters_) != 0) return true;
+ // Only a single GVN flag can be set when we have a parameter
+ // (with a possible exception of the special OsrEntries flag).
+ affected_flags &= ~(1 << HValue::kChangesOsrEntries);
+ ASSERT(IsPowerOf2(affected_flags));
+ for (int i = 0; i < parameters_.length(); i++) {
+ int flag = i << 1;
+ if (((1 << flag) & affected_flags) != 0) {
+ if (parameters_[i] == NULL) return true;
+ return parameters_[i]->Contains(value->GetGVNParameter());
+ }
+ }
+ return true;
+ }
+
+ int flags() const { return flags_; }
+
+ private:
+ typedef ZoneList<intptr_t> ParameterList;
+
+ static const int kParameterListLengthLimit = 8;
+
+ void AddWithoutParameter(int flags) {
+ AddFlags(flags);
+ flags_without_parameters_ |= flags;
+ }
+
+ void AddWithParameter(int flags, intptr_t parameter) {
+ AddFlags(flags);
+ if ((flags_without_parameters_ & flags) != 0) return;
+ int flag = -1;
+ for (int i = 0; i < HValue::kFirstNonGVNFlag; i += 2) {
+ if ((flags & (1 << i)) != 0) {
+ flag = i;
+ break;
+ }
+ }
+ ASSERT(flag != -1);
+ ASSERT(flags == (1 << flag));
+ InternalAddWithParameter(flag, parameter);
+ }
+
+ void InternalAddWithParameter(int flag, intptr_t parameter) {
+ int flag_index = flag >> 1;
+ ASSERT(flag == (flag_index << 1));
+ if (parameters_.length() <= flag_index) {
fschneider 2011/03/16 15:43:28 I find (flag_index >= parameters_.length()) better
+ parameters_.AddBlock(NULL, flag_index - parameters_.length() + 1);
+ }
+ if (parameters_[flag_index] == NULL) {
+ parameters_[flag_index] = new ParameterList(2);
+ } else if (parameters_[flag_index]->Contains(parameter)) {
+ return;
+ }
+ if (parameters_[flag_index]->length() == kParameterListLengthLimit) {
+ // Too many parameters to track efficiently.
+ parameters_[flag_index] = NULL;
+ flags_without_parameters_ |= (1 << flag);
+ return;
+ }
+ parameters_[flag_index]->Add(parameter);
+ }
+
+ void AddFlags(int flags) {
+ ASSERT((flags & HValue::ChangesFlagsMask()) == flags);
+ flags_ |= flags;
+ }
+
+ int flags_;
+ int flags_without_parameters_;
+ ZoneList<ParameterList*> parameters_;
+
+ DISALLOW_COPY_AND_ASSIGN(HEffectSet);
+};
+
HValueMap::HValueMap(const HValueMap* other)
: array_size_(other->array_size_),
@@ -1019,9 +1142,8 @@ HValueMap::HValueMap(const HValueMap* other)
}
-void HValueMap::Kill(int flags) {
- int depends_flags = HValue::ConvertChangesToDependsFlags(flags);
- if ((present_flags_ & depends_flags) == 0) return;
+void HValueMap::Kill(const HEffectSet& effects) {
+ if (!effects.HasEffectOnAny(present_flags_)) return;
present_flags_ = 0;
for (int i = 0; i < array_size_; ++i) {
HValue* value = array_[i].value;
@@ -1031,7 +1153,7 @@ void HValueMap::Kill(int flags) {
int next;
for (int current = array_[i].next; current != kNil; current = next) {
next = lists_[current].next;
- if ((lists_[current].value->flags() & depends_flags) != 0) {
+ if (effects.HasEffectOn(lists_[current].value)) {
// Drop it.
count_--;
lists_[current].next = free_list_head_;
@@ -1046,7 +1168,7 @@ void HValueMap::Kill(int flags) {
array_[i].next = kept;
// Now possibly drop directly indexed element.
- if ((array_[i].value->flags() & depends_flags) != 0) { // Drop it.
+ if (effects.HasEffectOn(array_[i].value)) {
count_--;
int head = array_[i].next;
if (head == kNil) {
@@ -1227,15 +1349,18 @@ void HStackCheckEliminator::RemoveStackCheck(HBasicBlock* block) {
class HGlobalValueNumberer BASE_EMBEDDED {
public:
- explicit HGlobalValueNumberer(HGraph* graph, CompilationInfo* info)
- : graph_(graph),
- info_(info),
- block_side_effects_(graph_->blocks()->length()),
- loop_side_effects_(graph_->blocks()->length()) {
+ HGlobalValueNumberer(HGraph* graph, CompilationInfo* info)
+ : graph_(graph), info_(info) {
ASSERT(Heap::allow_allocation(false));
- block_side_effects_.AddBlock(0, graph_->blocks()->length());
- loop_side_effects_.AddBlock(0, graph_->blocks()->length());
+ int length = graph_->blocks()->length();
+ block_side_effects_ = Zone::NewArray<HEffectSet>(length);
+ loop_side_effects_ = Zone::NewArray<HEffectSet>(length);
+ for (int i = 0; i < length; i++) {
+ block_side_effects_[i].Initialize();
+ loop_side_effects_[i].Initialize();
+ }
}
+
~HGlobalValueNumberer() {
ASSERT(!Heap::allow_allocation(true));
}
@@ -1248,7 +1373,7 @@ class HGlobalValueNumberer BASE_EMBEDDED {
void LoopInvariantCodeMotion();
void ProcessLoopBlock(HBasicBlock* block,
HBasicBlock* before_loop,
- int loop_kills);
+ const HEffectSet& loop_effects);
bool AllowCodeMotion();
bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header);
@@ -1258,11 +1383,11 @@ class HGlobalValueNumberer BASE_EMBEDDED {
HGraph* graph_;
CompilationInfo* info_;
- // A map of block IDs to their side effects.
- ZoneList<int> block_side_effects_;
+ // An array mapping block IDs to their side effects.
+ HEffectSet* block_side_effects_;
- // A map of loop header block IDs to their loop's side effects.
- ZoneList<int> loop_side_effects_;
+ // An array mapping loop header block IDs to their loop's side effects.
+ HEffectSet* loop_side_effects_;
};
@@ -1282,23 +1407,23 @@ void HGlobalValueNumberer::ComputeBlockSideEffects() {
HBasicBlock* block = graph_->blocks()->at(i);
HInstruction* instr = block->first();
int id = block->block_id();
- int side_effects = 0;
- while (instr != NULL) {
- side_effects |= (instr->flags() & HValue::ChangesFlagsMask());
- instr = instr->next();
- }
- block_side_effects_[id] |= side_effects;
+ HEffectSet* block_effects = &block_side_effects_[id];
// Loop headers are part of their loop.
- if (block->IsLoopHeader()) {
- loop_side_effects_[id] |= side_effects;
+ HEffectSet* loop_effects =
+ block->IsLoopHeader() ? &loop_side_effects_[id] : NULL;
+
+ while (instr != NULL) {
+ block_effects->Add(instr);
+ if (loop_effects != NULL) loop_effects->Add(instr);
+ instr = instr->next();
}
// Propagate loop side effects upwards.
if (block->HasParentLoopHeader()) {
int header_id = block->parent_loop_header()->block_id();
- loop_side_effects_[header_id] |=
- block->IsLoopHeader() ? loop_side_effects_[id] : side_effects;
+ loop_side_effects_[header_id].AddAll(
+ block->IsLoopHeader() ? *loop_effects : *block_effects);
}
}
}
@@ -1308,14 +1433,14 @@ void HGlobalValueNumberer::LoopInvariantCodeMotion() {
for (int i = graph_->blocks()->length() - 1; i >= 0; --i) {
HBasicBlock* block = graph_->blocks()->at(i);
if (block->IsLoopHeader()) {
- int side_effects = loop_side_effects_[block->block_id()];
+ const HEffectSet& loop_effects = loop_side_effects_[block->block_id()];
TraceGVN("Try loop invariant motion for block B%d effects=0x%x\n",
block->block_id(),
- side_effects);
+ loop_effects.flags());
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);
+ ProcessLoopBlock(graph_->blocks()->at(j), block, loop_effects);
}
}
}
@@ -1324,17 +1449,16 @@ void HGlobalValueNumberer::LoopInvariantCodeMotion() {
void HGlobalValueNumberer::ProcessLoopBlock(HBasicBlock* block,
HBasicBlock* loop_header,
- int loop_kills) {
+ const HEffectSet& loop_effects) {
HBasicBlock* pre_header = loop_header->predecessors()->at(0);
- int depends_flags = HValue::ConvertChangesToDependsFlags(loop_kills);
TraceGVN("Loop invariant motion for B%d depends_flags=0x%x\n",
block->block_id(),
- depends_flags);
+ loop_effects.flags());
HInstruction* instr = block->first();
while (instr != NULL) {
HInstruction* next = instr->next();
if (instr->CheckFlag(HValue::kUseGVN) &&
- (instr->flags() & depends_flags) == 0) {
+ !loop_effects.HasEffectOn(instr)) {
TraceGVN("Checking instruction %d (%s)\n",
instr->id(),
instr->Mnemonic());
@@ -1414,7 +1538,8 @@ void HGlobalValueNumberer::AnalyzeBlock(HBasicBlock* block, HValueMap* map) {
if (flags != 0) {
ASSERT(!instr->CheckFlag(HValue::kUseGVN));
// Clear all instructions in the map that are affected by side effects.
- map->Kill(flags);
+ HEffectSet effects(flags);
+ map->Kill(effects);
TraceGVN("Instruction %d kills\n", instr->id());
} else if (instr->CheckFlag(HValue::kUseGVN)) {
HValue* other = map->Lookup(instr);
@@ -1450,9 +1575,9 @@ void HGlobalValueNumberer::AnalyzeBlock(HBasicBlock* block, HValueMap* map) {
}
if (!is_successor) {
- int side_effects = 0;
+ HEffectSet side_effects;
for (int j = block->block_id() + 1; j < dominated->block_id(); ++j) {
- side_effects |= block_side_effects_[j];
+ side_effects.AddAll(block_side_effects_[j]);
}
successor_map->Kill(side_effects);
}
@@ -3034,10 +3159,7 @@ HInstruction* HGraphBuilder::BuildStoreNamedField(HValue* object,
new HStoreNamedField(object, name, value, is_in_object, offset);
if (lookup->type() == MAP_TRANSITION) {
Handle<Map> transition(lookup->GetTransitionMapFromMap(*type));
- instr->set_transition(transition);
- // TODO(fschneider): Record the new map type of the object in the IR to
- // enable elimination of redundant checks after the transition store.
- instr->SetFlag(HValue::kChangesMaps);
+ instr->SetTransition(transition);
}
return instr;
}
« no previous file with comments | « src/hydrogen.h ('k') | src/hydrogen-instructions.h » ('j') | src/hydrogen-instructions.h » ('J')

Powered by Google App Engine
This is Rietveld 408576698