Fixup redefinitions before doing code motion

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 465 matching lines @@
       for (PhiIterator it(join); !it.Done(); it.Advance()) {
         PhiInstr* phi = it.Current();
         ASSERT(phi != NULL);
         VerifyUseListsInInstruction(phi);
       }
     }
     for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
       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)
     : zone_(Thread::Current()->zone()),
       variable_count_(variable_count),
       postorder_(postorder),
       live_out_(postorder.length()),
       kill_(postorder.length()),
       live_in_(postorder.length()) {}
 
@@ skipping 1589 matching lines @@
                                     Definition* other) {
   for (Value::Iterator it(def->input_use_list()); !it.Done(); it.Advance()) {
     Value* use = it.Current();
     if (IsDominatedUse(dom, use)) {
       use->BindTo(other);
     }
   }
 }
 
 
+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())) {
     return Smi::Cast(const_instr->value()).Value() >= 0;
   }
   return false;
 }
 
 
 static BinarySmiOpInstr* AsSmiShiftLeftInstruction(Definition* d) {
@@ skipping 120 matching lines @@
                                                 Representation rep,
                                                 intptr_t cid) {
   ExtractNthOutputInstr* extract =
       new (Z) ExtractNthOutputInstr(new (Z) Value(instr), index, rep, cid);
   instr->ReplaceUsesWith(extract);
   InsertAfter(instr, extract, NULL, FlowGraph::kValue);
 }
 
 
 }  // namespace dart