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) &&
+          !isUsedAfterStores(stores[1], load)) {

[kasperl, 2011/12/22 15:11:54]

Is stores[1] guaranteed to be the last store. I guess so. Maybe pass all the
stores to the isUsedAfterStores and let that function deal with it. That makes
it easier to add a nice big comment that explains why you're using stores[1],
not stores.last(), or stores[3.14].

[ngeoffray, 2011/12/22 15:15:10]

On a loop phi we currently have the assumption that there are only two
predecessors: the entry (input 0), and the back edge (input 1). I added a
comment and an assert.

+        load.setGenerateAtUseSite();
+      }
+    } else {
       load.setGenerateAtUseSite();
     }
   }
 
+  bool isUsedAfterStores(HStore update, HLoad load) {
+    // [update] is the store of the loop phi for the back edge.
+    // [load] is the replacement of the loop phi.
+    for (HInstruction instruction in load.usedBy) {
+      if (instruction.block.id >= update.value.block.id) return true;
+    }
+    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;
   }
 }