Fix bug in load elimination with multiple phis.

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2013, 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_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/cpu.h"
 #include "vm/dart_entry.h"
@@ skipping 5606 matching lines @@
           input_place.set_id(places->length());
           result = Place::Wrap(input_place);
           map->Insert(result);
           places->Add(result);
           if (FLAG_trace_optimization) {
             OS::Print("  adding place %s as %" Pd "\n",
                       result->ToCString(),
                       result->id());
           }
         }
-
         phi_moves->CreateOutgoingMove(block->PredecessorAt(j),
                                       result->id(),
                                       place->id());
       }
     }
   }
 
   return phi_moves;
 }
 
@@ skipping 125 matching lines @@
     return forwarded_;
   }
 
   // Compute sets of loads generated and killed by each block.
   // Additionally compute upwards exposed and generated loads for each block.
   // Exposed loads are those that can be replaced if a corresponding
   // reaching load will be found.
   // Loads that are locally redundant will be replaced as we go through
   // instructions.
   void ComputeInitialSets() {
-    BitVector* forwarded_loads = new BitVector(aliased_set_->max_place_id());
-
     for (BlockIterator block_it = graph_->reverse_postorder_iterator();
          !block_it.Done();
          block_it.Advance()) {
       BlockEntryInstr* block = block_it.Current();
       const intptr_t preorder_number = block->preorder_number();
 
       BitVector* kill = kill_[preorder_number];
       BitVector* gen = gen_[preorder_number];
 
       ZoneGrowableArray<Definition*>* exposed_values = NULL;
@@ skipping 138 matching lines @@
 
           exposed_values->Add(defn);
         }
 
         gen->Add(place_id);
 
         if (out_values == NULL) out_values = CreateBlockOutValues();
         (*out_values)[place_id] = defn;
       }
 
-      PhiPlaceMoves::MovesList phi_moves =
-          aliased_set_->phi_moves()->GetOutgoingMoves(block);
-      if (phi_moves != NULL) {
-        PerformPhiMoves(phi_moves, gen, forwarded_loads);
-      }
-
       exposed_values_[preorder_number] = exposed_values;
       out_values_[preorder_number] = out_values;
     }
   }
 
   static void PerformPhiMoves(PhiPlaceMoves::MovesList phi_moves,
                               BitVector* out,
                               BitVector* forwarded_loads) {
     forwarded_loads->Clear();
 
@@ skipping 16 matching lines @@
     }
 
     out->AddAll(forwarded_loads);
   }
 
   // Compute OUT sets by propagating them iteratively until fix point
   // is reached.
   void ComputeOutSets() {
     BitVector* temp = new BitVector(aliased_set_->max_place_id());
     BitVector* forwarded_loads = new BitVector(aliased_set_->max_place_id());
+    BitVector* temp_out = new BitVector(aliased_set_->max_place_id());
 
     bool changed = true;
     while (changed) {
       changed = false;
 
       for (BlockIterator block_it = graph_->reverse_postorder_iterator();
            !block_it.Done();
            block_it.Advance()) {
         BlockEntryInstr* block = block_it.Current();
 
         const intptr_t preorder_number = block->preorder_number();
 
         BitVector* block_in = in_[preorder_number];
         BitVector* block_out = out_[preorder_number];
         BitVector* block_kill = kill_[preorder_number];
         BitVector* block_gen = gen_[preorder_number];
 
         // Compute block_in as the intersection of all out(p) where p
         // is a predecessor of the current block.
         if (block->IsGraphEntry()) {
           temp->Clear();
         } else {
           temp->SetAll();
           ASSERT(block->PredecessorCount() > 0);
           for (intptr_t i = 0; i < block->PredecessorCount(); i++) {
             BlockEntryInstr* pred = block->PredecessorAt(i);
             BitVector* pred_out = out_[pred->preorder_number()];
             if (pred_out != NULL) {

[Vyacheslav Egorov (Chromium), 2014/02/27 16:25:09]

I would write it slightly differently:

if (pred_out == NULL) continue;

PhiPlaceMoves::MovesList phi_moves =
aliased_set_->phi_moves()->GetOutgoingMoves(pred);
if (phi_moves != NULL) {
  // If there are phi moves, perform intersection with
  // a copy of pred_out where the phi moves are applied.
  temp_out->CopyFrom(pred_out);
  PerformPhiMoves(phi_moves, temp_out, forwarded_loads);
  pred_out = temp_out;
}

temp->Intersect(pred_out);

[Florian Schneider, 2014/02/28 13:38:57]

Done.

-              temp->Intersect(pred_out);
+              PhiPlaceMoves::MovesList phi_moves =
+                  aliased_set_->phi_moves()->GetOutgoingMoves(pred);
+              if (phi_moves != NULL) {
+                // If there are phi moves, perform intersection with
+                // a copy of pred_out where the phi moves are applied.
+                temp_out->CopyFrom(pred_out);
+                PerformPhiMoves(phi_moves, temp_out, forwarded_loads);
+                temp->Intersect(temp_out);
+              } else {
+                temp->Intersect(pred_out);
+              }
             }
           }
         }
 
         if (!temp->Equals(*block_in) || (block_out == NULL)) {
           // If IN set has changed propagate the change to OUT set.
           block_in->CopyFrom(temp);
 
           temp->RemoveAll(block_kill);
           temp->AddAll(block_gen);
 
-          PhiPlaceMoves::MovesList phi_moves =
-              aliased_set_->phi_moves()->GetOutgoingMoves(block);
-          if (phi_moves != NULL) {
-            PerformPhiMoves(phi_moves, temp, forwarded_loads);
-          }
-
           if ((block_out == NULL) || !block_out->Equals(*temp)) {
             if (block_out == NULL) {
               block_out = out_[preorder_number] =
                   new BitVector(aliased_set_->max_place_id());
             }
             block_out->CopyFrom(temp);
             changed = true;
           }
         }
       }
@@ skipping 2585 matching lines @@
   }
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits.length(); i++) {
     CreateMaterializationAt(exits[i], alloc, alloc->cls(), *fields);
   }
 }
 
 
 }  // namespace dart