Revision: 17196
Author: [email protected]
Date: Mon Oct 14 13:32:02 2013 UTC
Log: Reduce queue size in dead code elimination by eagerly processing
live instructions.
BUG=
[email protected]
Review URL: https://codereview.chromium.org/27178002
http://code.google.com/p/v8/source/detail?r=17196
Modified:
/branches/bleeding_edge/src/hydrogen-dce.cc
/branches/bleeding_edge/src/hydrogen-dce.h
=======================================
--- /branches/bleeding_edge/src/hydrogen-dce.cc Fri Aug 9 15:18:23 2013 UTC
+++ /branches/bleeding_edge/src/hydrogen-dce.cc Mon Oct 14 13:32:02 2013 UTC
@@ -31,56 +31,60 @@
namespace v8 {
namespace internal {
-bool HDeadCodeEliminationPhase::MarkLive(HValue* ref, HValue* instr) {
- if (instr->CheckFlag(HValue::kIsLive)) return false;
- instr->SetFlag(HValue::kIsLive);
+void HDeadCodeEliminationPhase::MarkLive(
+ HValue* instr, ZoneList<HValue*>* worklist) {
+ if (instr->CheckFlag(HValue::kIsLive)) return; // Already live.
- if (FLAG_trace_dead_code_elimination) {
- HeapStringAllocator allocator;
- StringStream stream(&allocator);
- if (ref != NULL) {
- ref->PrintTo(&stream);
- } else {
- stream.Add("root ");
+ if (FLAG_trace_dead_code_elimination) PrintLive(NULL, instr);
+
+ // Transitively mark all inputs of live instructions live.
+ worklist->Add(instr, zone());
+ while (!worklist->is_empty()) {
+ HValue* instr = worklist->RemoveLast();
+ instr->SetFlag(HValue::kIsLive);
+ for (int i = 0; i < instr->OperandCount(); ++i) {
+ HValue* input = instr->OperandAt(i);
+ if (!input->CheckFlag(HValue::kIsLive)) {
+ input->SetFlag(HValue::kIsLive);
+ worklist->Add(input, zone());
+ if (FLAG_trace_dead_code_elimination) PrintLive(instr, input);
+ }
}
- stream.Add(" -> ");
- instr->PrintTo(&stream);
- PrintF("[MarkLive %s]\n", *stream.ToCString());
}
+}
- return true;
+
+void HDeadCodeEliminationPhase::PrintLive(HValue* ref, HValue* instr) {
+ HeapStringAllocator allocator;
+ StringStream stream(&allocator);
+ if (ref != NULL) {
+ ref->PrintTo(&stream);
+ } else {
+ stream.Add("root ");
+ }
+ stream.Add(" -> ");
+ instr->PrintTo(&stream);
+ PrintF("[MarkLive %s]\n", *stream.ToCString());
}
void HDeadCodeEliminationPhase::MarkLiveInstructions() {
- ZoneList<HValue*> worklist(graph()->blocks()->length(), zone());
+ ZoneList<HValue*> worklist(10, zone());
- // Mark initial root instructions for dead code elimination.
+ // Transitively mark all live instructions, starting from roots.
for (int i = 0; i < graph()->blocks()->length(); ++i) {
HBasicBlock* block = graph()->blocks()->at(i);
for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
HInstruction* instr = it.Current();
- if (instr->CannotBeEliminated() && MarkLive(NULL, instr)) {
- worklist.Add(instr, zone());
- }
+ if (instr->CannotBeEliminated()) MarkLive(instr, &worklist);
}
for (int j = 0; j < block->phis()->length(); j++) {
HPhi* phi = block->phis()->at(j);
- if (phi->CannotBeEliminated() && MarkLive(NULL, phi)) {
- worklist.Add(phi, zone());
- }
+ if (phi->CannotBeEliminated()) MarkLive(phi, &worklist);
}
}
- // Transitively mark all inputs of live instructions live.
- while (!worklist.is_empty()) {
- HValue* instr = worklist.RemoveLast();
- for (int i = 0; i < instr->OperandCount(); ++i) {
- if (MarkLive(instr, instr->OperandAt(i))) {
- worklist.Add(instr->OperandAt(i), zone());
- }
- }
- }
+ ASSERT(worklist.is_empty()); // Should have processed everything.
}
=======================================
--- /branches/bleeding_edge/src/hydrogen-dce.h Sun Jul 7 06:00:15 2013 UTC
+++ /branches/bleeding_edge/src/hydrogen-dce.h Mon Oct 14 13:32:02 2013 UTC
@@ -45,7 +45,8 @@
}
private:
- bool MarkLive(HValue* ref, HValue* instr);
+ void MarkLive(HValue* instr, ZoneList<HValue*>* worklist);
+ void PrintLive(HValue* ref, HValue* instr);
void MarkLiveInstructions();
void RemoveDeadInstructions();
};
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
