1// Copyright 2013 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#include "hydrogen-redundant-phi.h"
29
30namespace v8 {
31namespace internal {
32
33void HRedundantPhiEliminationPhase::Run() {
34  // Gather all phis from all blocks first.
35  const ZoneList<HBasicBlock*>* blocks(graph()->blocks());
36  ZoneList<HPhi*> all_phis(blocks->length(), zone());
37  for (int i = 0; i < blocks->length(); ++i) {
38    HBasicBlock* block = blocks->at(i);
39    for (int j = 0; j < block->phis()->length(); j++) {
40      all_phis.Add(block->phis()->at(j), zone());
41    }
42  }
43
44  // Iteratively reduce all phis in the list.
45  ProcessPhis(&all_phis);
46
47#if DEBUG
48  // Make sure that we *really* removed all redundant phis.
49  for (int i = 0; i < blocks->length(); ++i) {
50    for (int j = 0; j < blocks->at(i)->phis()->length(); j++) {
51      ASSERT(blocks->at(i)->phis()->at(j)->GetRedundantReplacement() == NULL);
52    }
53  }
54#endif
55}
56
57
58void HRedundantPhiEliminationPhase::ProcessBlock(HBasicBlock* block) {
59  ProcessPhis(block->phis());
60}
61
62
63void HRedundantPhiEliminationPhase::ProcessPhis(const ZoneList<HPhi*>* phis) {
64  bool updated;
65  do {
66    // Iterately replace all redundant phis in the given list.
67    updated = false;
68    for (int i = 0; i < phis->length(); i++) {
69      HPhi* phi = phis->at(i);
70      if (phi->CheckFlag(HValue::kIsDead)) continue;  // Already replaced.
71
72      HValue* replacement = phi->GetRedundantReplacement();
73      if (replacement != NULL) {
74        phi->SetFlag(HValue::kIsDead);
75        for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) {
76          HValue* value = it.value();
77          value->SetOperandAt(it.index(), replacement);
78          // Iterate again if used in another non-dead phi.
79          updated |= value->IsPhi() && !value->CheckFlag(HValue::kIsDead);
80        }
81        phi->block()->RemovePhi(phi);
82      }
83    }
84  } while (updated);
85}
86
87
88} }  // namespace v8::internal
89