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

Index: dart/frog/leg/ssa/phi_eliminator.dart
===================================================================
--- dart/frog/leg/ssa/phi_eliminator.dart	(revision 2759)
+++ dart/frog/leg/ssa/phi_eliminator.dart	(working copy)
@@ -125,11 +125,47 @@
     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.