Fix bug in receiver-phi computation.

runtime/vm/flow_graph.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/flow_graph.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
@@ skipping 355 matching lines @@
       ASSERT(instr->IsBlockEntry() ||
              (instr->IsPhi() && instr->AsPhi()->is_alive()) ||
              (instr->previous() != NULL));
       prev = curr;
       curr = curr->next_use();
     }
   }
 }
 
 
-void FlowGraph::ComputeIsReceiverRecursive(PhiInstr* phi,
-                                           BitVector* processed) const {
-  if (phi->is_receiver() != PhiInstr::kUnknownReceiver) return;
-  if (processed->Contains(phi->ssa_temp_index())) return;
-  processed->Add(phi->ssa_temp_index());
-  for (intptr_t i = 0; i < phi->InputCount(); ++i) {
-    Definition* def = phi->InputAt(i)->definition();
-    if (def->IsParameter() && (def->AsParameter()->index() == 0)) continue;
-    if (!def->IsPhi()) {
-      phi->set_is_receiver(PhiInstr::kNotReceiver);
-      return;
-    }
-    ComputeIsReceiverRecursive(def->AsPhi(), processed);
-    if (def->AsPhi()->is_receiver() == PhiInstr::kNotReceiver) {
-      phi->set_is_receiver(PhiInstr::kNotReceiver);
-      return;
+void FlowGraph::ComputeIsReceiver() const {
+  GrowableArray<PhiInstr*> worklist;
+  BitVector* processed =
+      new(zone()) BitVector(zone(), max_virtual_register_number());
+  for (BlockIterator block_it = reverse_postorder_iterator();
+       !block_it.Done();
+       block_it.Advance()) {
+    BlockEntryInstr* entry = block_it.Current();
+    JoinEntryInstr* join_entry = entry->AsJoinEntry();
+    if (join_entry != NULL) {
+      for (PhiIterator it(join_entry); !it.Done(); it.Advance()) {
+        PhiInstr* phi = it.Current();
+        phi->set_is_receiver(PhiInstr::kReceiver);
+        for (intptr_t i = 0; i < phi->InputCount(); ++i) {
+          Definition* def = phi->InputAt(i)->definition();
+          if (def->IsParameter() && (def->AsParameter()->index() == 0)) {
+            continue;
+          }
+          if (!def->IsPhi()) {
+            phi->set_is_receiver(PhiInstr::kNotReceiver);
+            worklist.Add(phi);
+            processed->Add(phi->ssa_temp_index());
+            break;
+          }
+        }
+      }
     }
   }
-  phi->set_is_receiver(PhiInstr::kReceiver);
+
+  while (!worklist.is_empty()) {
+    PhiInstr* phi = worklist.RemoveLast();
+    for (Value::Iterator it(phi->input_use_list());
+         !it.Done();
+         it.Advance()) {
+      PhiInstr* use = it.Current()->instruction()->AsPhi();
+      if ((use != NULL) && !processed->Contains(use->ssa_temp_index())) {
+        use->set_is_receiver(PhiInstr::kNotReceiver);
+        worklist.Add(use);
+        processed->Add(use->ssa_temp_index());
+      }
+    }
+  }
 }
 
 
 bool FlowGraph::IsReceiver(Definition* def) const {
   if (def->IsParameter()) return (def->AsParameter()->index() == 0);
   if (!def->IsPhi()) return false;
   PhiInstr* phi = def->AsPhi();
   if (phi->is_receiver() != PhiInstr::kUnknownReceiver) {
     return (phi->is_receiver() == PhiInstr::kReceiver);
   }
   // Not known if this phi is the receiver yet. Compute it now.
-  BitVector* processed =
-      new(zone()) BitVector(zone(), max_virtual_register_number());
-  ComputeIsReceiverRecursive(phi, processed);
+  ComputeIsReceiver();

[Vyacheslav Egorov (Google), 2016/04/01 11:07:59]

I still think it is much better to just fix the existing algorithm instead of
revisiting the whole graph:

void FlowGraph::ComputeIsReceiverRecursive(PhiInstr* phi,
                                           GrowableArray<PhiInstr*>* unmark)
const {
  if (phi->is_receiver() != PhiInstr::kUnknownReceiver) return;
  phi->set_is_receiver(PhiInstr::kReceiver);
  for (intptr_t i = 0; i < phi->InputCount(); ++i) {
    Definition* def = phi->InputAt(i)->definition();
    if (def->IsParameter() && (def->AsParameter()->index() == 0)) continue;
    if (!def->IsPhi()) {
      phi->set_is_receiver(PhiInstr::kNotReceiver);
      break;
    }
    ComputeIsReceiverRecursive(def->AsPhi(), unmark);
    if (def->AsPhi()->is_receiver() == PhiInstr::kNotReceiver) {
      phi->set_is_receiver(PhiInstr::kNotReceiver);
      break;
    }
  }

  if (phi->is_receiver() == PhiInstr::kNotReceiver) {
    unmark->Add(phi);
  }
}

void FlowGraph::ComputeIsReceiver(PhiInstr* phi) const {
  GrowableArray<PhiInstr*> unmark;
  ComputeIsReceiverRecursive(phi, &unmark);

  // Now drain unmark.
  while (!unmark.is_empty()) {
    PhiInstr* phi = unmark.RemoveLast();
    for (Value::Iterator it(phi->input_use_list());
         !it.Done();
         it.Advance()) {
      PhiInstr* use = it.Current()->instruction()->AsPhi();
      if ((use != NULL) && (use->is_receiver() == kReceiver)) {
        use->set_is_receiver(PhiInstr::kNotReceiver);
        unmark.Add(use);
      }
    }
  } 
}

   return (phi->is_receiver() == PhiInstr::kReceiver);
 }
 
 
 // Use CHA to determine if the call needs a class check: if the callee's
 // receiver is the same as the caller's receiver and there are no overriden
 // callee functions, then no class check is needed.
 bool FlowGraph::InstanceCallNeedsClassCheck(InstanceCallInstr* call,
                                             RawFunction::Kind kind) const {
   if (!FLAG_use_cha_deopt && !isolate()->all_classes_finalized()) {
@@ skipping 1624 matching lines @@
         ReplaceCurrentInstruction(&it, current, replacement);
         changed = true;
       }
     }
   }
   return changed;
 }
 
 
 }  // namespace dart