Improve dead code elimination by transitively marking live code and removing all dead code. Replace…

src/hydrogen.cc

 // Copyright 2012 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
@@ skipping 86 matching lines @@
 void HBasicBlock::AddPhi(HPhi* phi) {
   ASSERT(!IsStartBlock());
   phis_.Add(phi, zone());
   phi->SetBlock(this);
 }
 
 
 void HBasicBlock::RemovePhi(HPhi* phi) {
   ASSERT(phi->block() == this);
   ASSERT(phis_.Contains(phi));
-  ASSERT(phi->HasNoUses() || !phi->is_live());
   phi->Kill();
   phis_.RemoveElement(phi);
   phi->SetBlock(NULL);
 }
 
 
 void HBasicBlock::AddInstruction(HInstruction* instr) {
   ASSERT(!IsStartBlock() || !IsFinished());
   ASSERT(!instr->IsLinked());
   ASSERT(!IsFinished());
@@ skipping 2469 matching lines @@
   // Make sure that we *really* removed all redundant phis.
   for (int i = 0; i < blocks_.length(); ++i) {
     for (int j = 0; j < blocks_[i]->phis()->length(); j++) {
       ASSERT(blocks_[i]->phis()->at(j)->GetRedundantReplacement() == NULL);
     }
   }
 #endif
 }
 
 
-void HGraph::EliminateUnreachablePhis() {
-  HPhase phase("H_Unreachable phi elimination", this);
-
-  // Initialize worklist.
-  ZoneList<HPhi*> phi_list(blocks_.length(), zone());
-  ZoneList<HPhi*> worklist(blocks_.length(), zone());
-  for (int i = 0; i < blocks_.length(); ++i) {
-    for (int j = 0; j < blocks_[i]->phis()->length(); j++) {
-      HPhi* phi = blocks_[i]->phis()->at(j);
-      phi_list.Add(phi, zone());
-      // We can't eliminate phis in the receiver position in the environment
-      // because in case of throwing an error we need this value to
-      // construct a stack trace.
-      if (phi->HasRealUses() || phi->IsReceiver())  {
-        phi->set_is_live(true);
-        worklist.Add(phi, zone());
-      }
-    }
-  }
-
-  // Iteratively mark live phis.
-  while (!worklist.is_empty()) {
-    HPhi* phi = worklist.RemoveLast();
-    for (int i = 0; i < phi->OperandCount(); i++) {
-      HValue* operand = phi->OperandAt(i);
-      if (operand->IsPhi() && !HPhi::cast(operand)->is_live()) {
-        HPhi::cast(operand)->set_is_live(true);
-        worklist.Add(HPhi::cast(operand), zone());
-      }
-    }
-  }
-
-  // Remove unreachable phis.
-  for (int i = 0; i < phi_list.length(); i++) {
-    HPhi* phi = phi_list[i];
-    if (!phi->is_live()) {
-      HBasicBlock* block = phi->block();
-      block->RemovePhi(phi);
-      block->RecordDeletedPhi(phi->merged_index());
-    }
-  }
-}
-
-
 bool HGraph::CheckArgumentsPhiUses() {
   int block_count = blocks_.length();
   for (int i = 0; i < block_count; ++i) {
     for (int j = 0; j < blocks_[i]->phis()->length(); ++j) {
       HPhi* phi = blocks_[i]->phis()->at(j);
       // We don't support phi uses of arguments for now.
       if (phi->CheckFlag(HValue::kIsArguments)) return false;
     }
   }
   return true;
@@ skipping 2240 matching lines @@
     *bailout_reason = SmartArrayPointer<char>(StrDup(
         "Unsupported phi use of const variable"));
     return false;
   }
   EliminateRedundantPhis();
   if (!CheckArgumentsPhiUses()) {
     *bailout_reason = SmartArrayPointer<char>(StrDup(
         "Unsupported phi use of arguments"));
     return false;
   }
-  if (FLAG_eliminate_dead_phis) EliminateUnreachablePhis();
+
+  // Remove dead code and phis
+  if (FLAG_dead_code_elimination) DeadCodeElimination();
   CollectPhis();
 
   if (has_osr_loop_entry()) {
     const ZoneList<HPhi*>* phis = osr_loop_entry()->phis();
     for (int j = 0; j < phis->length(); j++) {
       HPhi* phi = phis->at(j);
       osr_values()->at(phi->merged_index())->set_incoming_value(phi);
     }
   }
 
@@ skipping 504 matching lines @@
         array_instruction = static_cast<ArrayInstructionInterface*>(op);
       } else {
         continue;
       }
       DehoistArrayIndex(array_instruction);
     }
   }
 }
 
 
+void HGraph::MarkLive(HValue *ref, HValue* instr,
+    ZoneList<HValue*>* worklist) {
+  if (!instr->CheckFlag(HValue::kIsLive)) {
+    instr->SetFlag(HValue::kIsLive);
+    worklist->Add(instr, zone());
+
+    if (FLAG_trace_dead_code_elimination) {
+      HeapStringAllocator allocator;
+      StringStream stream(&allocator);
+      if (ref != NULL) ref->PrintNameTo(&stream);

[Sven Panne, 2013/05/13 09:31:55]

Please print the full instruction here, not just the variable name, otherwise
the output is not very helpful. Same for instr below. (We did this previously
BTW).

[titzer, 2013/05/13 13:29:39]

Done.

[Sven Panne, 2013/05/13 14:55:52]

Again, I don't see the "Done" part, perhaps you forgot to upload a new version?

[titzer, 2013/05/13 18:11:13]

...

+      stream.Add(" -> ");
+      instr->PrintNameTo(&stream);
+      PrintF("[MarkLive %s]\n", *stream.ToCString());
+    }
+  }
+}
+
+
+bool HGraph::TryDeadCodeElimination(HValue* instr) {

[Sven Panne, 2013/05/13 09:31:55]

I think this helper method is actually less clear than inlining it at its call
sites and simplifying the resulting code.

[titzer, 2013/05/13 13:29:39]

I would go for inlining if it weren't used in two places.

[Sven Panne, 2013/05/13 14:55:52]

If you insist of keeping it, then make it at least remove the boolean return
value, it's a bit confusing. Instead just check if you've removed a phi and if
yes, call RecordDeletedPhi on the phi's block. Renaming this helper function to
"RemoveIfDead" (or something like this) would be nice, too.

[titzer, 2013/05/13 18:11:13]

I've inlined it and split the main algorithm into two methods.

+  if (!instr->CheckFlag(HValue::kIsLive)) {
+    // Instruction has not been marked live; assume it is dead and remove.
+    // TODO(titzer): we don't remove constants because some special constants
+    // might be used by later phases and are assumed to be in the graph
+    if (!instr->IsConstant()) instr->DeleteAndReplaceWith(NULL);
+    return true;
+  } else {
+    // Clear the liveness flag to leave the graph clean for the next DCE.
+    instr->ClearFlag(HValue::kIsLive);
+    return false;
+  }
+}
+
+
 void HGraph::DeadCodeElimination() {
   HPhase phase("H_Dead code elimination", this);

[Sven Panne, 2013/05/13 09:31:55]

We call this phase twice, so it would be good to name these differently, making
the visualizer output more readable. Note that HPhase doesn't keep a copy of the
string, just a pointer.

[titzer, 2013/05/13 13:29:39]

Done.

[Sven Panne, 2013/05/13 14:55:52]

Where? :-)

[titzer, 2013/05/13 18:11:13]

Done.

-  ZoneList<HInstruction*> worklist(blocks_.length(), zone());
+  ZoneList<HValue*> worklist(blocks_.length(), zone());
+  ZoneList<HPhi*> philist(blocks_.length(), zone());

[Sven Panne, 2013/05/13 09:31:55]

As Jakob already pointed out, I don't think we need this, see below.

[titzer, 2013/05/13 13:29:39]

I forgot to hit "send" on a previous set of comments. Maybe it will come this
time. But at any rate, we process the phis separately to avoid mutating the phi
list for a block as we iterate over it.

[Sven Panne, 2013/05/13 14:55:52]

Then rename it to phi_snapshot, making it's purpose clear.

[titzer, 2013/05/13 18:11:13]

I'm going with your latter suggestion to make a separate list of dead phis.

+
+  // Mark initial root instructions for dead code elimination.

[Sven Panne, 2013/05/13 09:31:55]

Replace this comment and the ones below by extracted methods with explanatory
names (just proposals below):

   MarkRoots(&worklist);
   MarkLive(&worklist);
   Sweep();

http://www.refactoring.com/catalog/extractMethod.html ;-)

[titzer, 2013/05/13 13:29:39]

Normally I would agree with breaking things into smaller methods (especially if
those methods can then be reused), but my opinion in this case is that the
overhead of adding the declarations here and in the header file aren't worth the
savings.

[Sven Panne, 2013/05/13 14:55:52]

In my opinion this is a *very* worthwhile refactoring: If you feel the slightest
urge to comment something (as you obviously do), don't comment it, but refactor
it instead. In the words of the famous Uncle Bob: Comments are a sign of our
inability to express our thoughts in code. :-)

One could even go as far as insisting on making every compiler phase a separate
class, which we should probably do in the future. In that case, the functions I
proposed would be the natural private helper functions.

[titzer, 2013/05/13 18:11:13]

I'm gonna go ahead and disagree with Bob on this one and leave my comments in.
In the future, I will endeavor to have fewer thoughts :)
Another day, perhaps.

   for (int i = 0; i < blocks()->length(); ++i) {
-    for (HInstruction* instr = blocks()->at(i)->first();
+    HBasicBlock* block = blocks()->at(i);
+    for (HInstruction* instr = block->first();
          instr != NULL;
          instr = instr->next()) {
-      if (instr->IsDead()) worklist.Add(instr, zone());
+      if (!instr->CanBeEliminated()) MarkLive(NULL, instr, &worklist);
+    }
+    // TODO(titzer): we can't eliminate the receiver for generating backtraces
+    for (int j = 0; j < block->phis()->length(); j++) {
+      HPhi* phi = block->phis()->at(j);
+      if (phi->IsReceiver()) MarkLive(NULL, phi, &worklist);
+      philist.Add(phi, zone());
     }
   }
 
+  // Transitively mark all inputs of live instructions live.
   while (!worklist.is_empty()) {
-    HInstruction* instr = worklist.RemoveLast();
-    // This happens when an instruction is used multiple times as operand. That
-    // in turn could happen through GVN.
-    if (!instr->IsLinked()) continue;
-    if (FLAG_trace_dead_code_elimination) {
-      HeapStringAllocator allocator;
-      StringStream stream(&allocator);
-      instr->PrintNameTo(&stream);
-      stream.Add(" = ");
-      instr->PrintTo(&stream);
-      PrintF("[removing dead instruction %s]\n", *stream.ToCString());
+    HValue* instr = worklist.RemoveLast();
+    for (int i = 0; i < instr->OperandCount(); ++i) {
+      MarkLive(instr, instr->OperandAt(i), &worklist);
     }
-    instr->DeleteAndReplaceWith(NULL);
-    for (int i = 0; i < instr->OperandCount(); ++i) {
-      HValue* operand = instr->OperandAt(i);
-      if (operand->IsDead()) worklist.Add(HInstruction::cast(operand), zone());
+  }
+
+  // Remove any instruction not marked in the previous phase.
+  for (int i = 0; i < blocks()->length(); ++i) {
+    HBasicBlock* block = blocks()->at(i);
+    for (HInstruction* instr = block->first();
+         instr != NULL;
+         instr = instr->next()) {
+      TryDeadCodeElimination(instr);
+    }
+  }
+
+  // Process phis separately because dead ones need to be recorded.
+  while (!philist.is_empty()) {

[Sven Panne, 2013/05/13 09:31:55]

Just fold this into the previous loop, no need for a separate list.

[titzer, 2013/05/13 13:29:39]

See above; we can't because the phi list of a block changes as we remove items
from it.

[Sven Panne, 2013/05/13 14:55:52]

An alternative approach would be folding this into the previous loop and
collecting the phis to nuke in a (probably very small) list, and iterate over
that list later to actually kill them. But I leave that up to you...

[titzer, 2013/05/13 18:11:13]

Yeah, that's a better idea.

+    HPhi* phi = philist.RemoveLast();
+    HBasicBlock* block = phi->block();
+    if (TryDeadCodeElimination(phi)) {
+      block->RecordDeletedPhi(phi->merged_index());
     }
   }
 }
 
 
 void HGraph::RestoreActualValues() {
   HPhase phase("H_Restore actual values", this);
 
   for (int block_index = 0; block_index < blocks()->length(); block_index++) {
     HBasicBlock* block = blocks()->at(block_index);
@@ skipping 6809 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal