Fixup redefinitions before doing code motion

runtime/vm/flow_graph.cc

Index: runtime/vm/flow_graph.cc
diff --git a/runtime/vm/flow_graph.cc b/runtime/vm/flow_graph.cc
index 16ed1ebacf2ba492cc0366c771511fe4e3790cf0..832baba2bacb05286d00cf2f5bd8d204220b23cf 100644
--- a/runtime/vm/flow_graph.cc
+++ b/runtime/vm/flow_graph.cc
@@ -483,10 +483,40 @@ bool FlowGraph::VerifyUseLists() {
       VerifyUseListsInInstruction(it.Current());
     }
   }
+
   return true;  // Return true so we can ASSERT validation.
 }
 
 
+// Verify that a redefinition domiates all uses of the redefined value.

[Vyacheslav Egorov (Google), 2017/02/23 13:47:27]

s/domiates/dominates/

[Florian Schneider, 2017/02/23 19:26:35]

Done.

+bool FlowGraph::VerifyRedefinitions() {
+  for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
+       block_it.Advance()) {
+    for (ForwardInstructionIterator instr_it(block_it.Current());
+         !instr_it.Done(); instr_it.Advance()) {
+      RedefinitionInstr* redefinition = instr_it.Current()->AsRedefinition();
+      if (redefinition != NULL) {
+        Definition* original = redefinition->value()->definition();
+        for (Value::Iterator it(original->input_use_list()); !it.Done();
+             it.Advance()) {
+          Value* original_use = it.Current();
+          if (original_use->instruction() == redefinition) {
+            continue;
+          }
+          if (original_use->instruction()->IsDominatedBy(redefinition)) {
+            FlowGraphPrinter::PrintGraph("VerifyRedefinitions", this);
+            THR_Print("%s\n", redefinition->ToCString());
+            THR_Print("use=%s\n", original_use->instruction()->ToCString());
+            return false;
+          }
+        }
+      }
+    }
+  }
+  return true;
+}
+
+
 LivenessAnalysis::LivenessAnalysis(
     intptr_t variable_count,
     const GrowableArray<BlockEntryInstr*>& postorder)
@@ -2096,6 +2126,21 @@ void FlowGraph::RenameDominatedUses(Definition* def,
 }
 
 
+void FlowGraph::FixupRedefinitions() {

[Vyacheslav Egorov (Google), 2017/02/23 13:47:27]

FixupRedefinitions(...) is a confusing name - maybe
RedefineUsesDominatedByRedefinitions() or something like that.

[Florian Schneider, 2017/02/23 19:26:36]

Done.

+  for (BlockIterator block_it = reverse_postorder_iterator(); !block_it.Done();
+       block_it.Advance()) {
+    for (ForwardInstructionIterator instr_it(block_it.Current());
+         !instr_it.Done(); instr_it.Advance()) {
+      RedefinitionInstr* redefinition = instr_it.Current()->AsRedefinition();
+      if (redefinition != NULL) {
+        Definition* original = redefinition->value()->definition();

[Vyacheslav Egorov (Google), 2017/02/23 13:47:27]

Can we have multiple Redefinitions(), e.g.

v0 <- something

| v1 <- Redefinition(v0)
|
| | v2 <- Redefinition(v0)
| |
| | use(v1)

in this case we will not rename use(v1) to v2 which might lead to incorrect code
motion. 

[Florian Schneider, 2017/02/23 19:26:35]

I have not seen this case: I think if redefinitions are properly inserted, v2
would redefine v1 if there is a dependency. Otherwise the two are independent.
How about we do CSE of redefinitions to make sure that it does not occur?

[Vyacheslav Egorov (Google), 2017/02/23 20:53:18]

I think this can occur in the situation like this:

class A {
  foo(obj) => obj.x();
}

bar(obj) {
  obj.foo(obj); // inline foo polymorphically here and then inline obj.x
polymorphically
}

but then our type propagation will take care of it.

I did not try to craft example where it goes south, but I will try.

+        RenameDominatedUses(original, redefinition, redefinition);
+      }
+    }
+  }
+}
+
+
 static bool IsPositiveOrZeroSmiConst(Definition* d) {
   ConstantInstr* const_instr = d->AsConstant();
   if ((const_instr != NULL) && (const_instr->value().IsSmi())) {