New bugfix for phi eliminator: if a loop phi is used after its update, the load of the phi must n...

dart/frog/leg/ssa/phi_eliminator.dart

 // Copyright (c) 2011, 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.
 
 class SsaPhiEliminator extends HGraphVisitor {
   HBasicBlock entry;
   HBasicBlock currentBlock;
 
   visitGraph(HGraph graph) {
     entry = graph.entry;
@@ skipping 107 matching lines @@
     // We propagate the type of the phi to the load instruction rather
     // than the local because we may end up sharing a single local
     // between different phis of different types.
     HLoad load = new HLoad(local, phi.type);
     loads.add(load);
 
     currentBlock.addAtEntry(load);
     currentBlock.rewrite(phi, load);
     currentBlock.removePhi(phi);
 
-    if (!currentBlock.isLoopHeader() || !hasLoopPhiAsInput(stores, loads)) {
+    if (currentBlock.isLoopHeader()) {
+      if (!hasLoopPhiAsInput(stores, loads) &&
+          !isPhiUsedInLoop(stores, load)) {
+        load.setGenerateAtUseSite();
+      }
+    } else {
       load.setGenerateAtUseSite();
     }
   }
 
+  bool isPhiUsedInLoop(List<HStore> stores, HLoad load) {
+    // [stores] contains the stores of a specific phi.
+    // [load] is the replacement of the loop phi.
+    // We assume a loop header only has two predecessors: the entry
+    // and the backedge.
+    assert(stores.length == 2);
+    HStore update = stores[1];
+    for (HInstruction instruction in load.usedBy) {
+      if (instruction.block.parentLoopHeader != update.block.parentLoopHeader) {

[floitsch, 2011/12/22 16:30:56]

What about nested loops? Then the parentLoopHeader is different, but the load
would still be used inside the loop.

+        continue;
+      }
+      if (instruction.block.id > update.block.id) return true;
+      if (instruction.block == update.block && isBefore(update, instruction)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  bool isBefore(HInstruction first, HInstruction second) {
+    assert(first.block == second.block);
+    HInstruction current = first.block.first;
+    while (current != null) {
+      if (current == first) return true;
+      if (current == second) return false;
+      current = current.next;
+    }
+    // In case the instructions are out of the block.
+    return false;
+  }
+
   bool hasLoopPhiAsInput(List<HStore> stores, List<HLoad> loads) {
     // [stores] contains the stores of a specific phi.
     // [loads] contains the phis that were converted to loads.
     assert(currentBlock.isLoopHeader());
     for (HStore store in stores) {
       HInstruction value = store.value;
       if (value is HPhi && value.block == currentBlock) {
         return true;
       } else if (value is HLoad && loads.indexOf(value) != -1) {
         return true;
       }
     }
     return false;
   }
 }