1// Copyright 2013 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/hydrogen-redundant-phi.h"
6
7namespace v8 {
8namespace internal {
9
10void HRedundantPhiEliminationPhase::Run() {
11  // Gather all phis from all blocks first.
12  const ZoneList<HBasicBlock*>* blocks(graph()->blocks());
13  ZoneList<HPhi*> all_phis(blocks->length(), zone());
14  for (int i = 0; i < blocks->length(); ++i) {
15    HBasicBlock* block = blocks->at(i);
16    for (int j = 0; j < block->phis()->length(); j++) {
17      all_phis.Add(block->phis()->at(j), zone());
18    }
19  }
20
21  // Iteratively reduce all phis in the list.
22  ProcessPhis(&all_phis);
23
24#if DEBUG
25  // Make sure that we *really* removed all redundant phis.
26  for (int i = 0; i < blocks->length(); ++i) {
27    for (int j = 0; j < blocks->at(i)->phis()->length(); j++) {
28      DCHECK(blocks->at(i)->phis()->at(j)->GetRedundantReplacement() == NULL);
29    }
30  }
31#endif
32}
33
34
35void HRedundantPhiEliminationPhase::ProcessBlock(HBasicBlock* block) {
36  ProcessPhis(block->phis());
37}
38
39
40void HRedundantPhiEliminationPhase::ProcessPhis(const ZoneList<HPhi*>* phis) {
41  bool updated;
42  do {
43    // Iterately replace all redundant phis in the given list.
44    updated = false;
45    for (int i = 0; i < phis->length(); i++) {
46      HPhi* phi = phis->at(i);
47      if (phi->CheckFlag(HValue::kIsDead)) continue;  // Already replaced.
48
49      HValue* replacement = phi->GetRedundantReplacement();
50      if (replacement != NULL) {
51        phi->SetFlag(HValue::kIsDead);
52        for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) {
53          HValue* value = it.value();
54          value->SetOperandAt(it.index(), replacement);
55          // Iterate again if used in another non-dead phi.
56          updated |= value->IsPhi() && !value->CheckFlag(HValue::kIsDead);
57        }
58        phi->block()->RemovePhi(phi);
59      }
60    }
61  } while (updated);
62}
63
64
65} }  // namespace v8::internal
66