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  // We do a simple fixed point iteration without any work list, because
35  // machine-generated JavaScript can lead to a very dense Hydrogen graph with
36  // an enormous work list and will consequently result in OOM. Experiments
37  // showed that this simple algorithm is good enough, and even e.g. tracking
38  // the set or range of blocks to consider is not a real improvement.
39  bool need_another_iteration;
40  const ZoneList<HBasicBlock*>* blocks(graph()->blocks());
41  ZoneList<HPhi*> redundant_phis(blocks->length(), zone());
42  do {
43    need_another_iteration = false;
44    for (int i = 0; i < blocks->length(); ++i) {
45      HBasicBlock* block = blocks->at(i);
46      for (int j = 0; j < block->phis()->length(); j++) {
47        HPhi* phi = block->phis()->at(j);
48        HValue* replacement = phi->GetRedundantReplacement();
49        if (replacement != NULL) {
50          // Remember phi to avoid concurrent modification of the block's phis.
51          redundant_phis.Add(phi, zone());
52          for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) {
53            HValue* value = it.value();
54            value->SetOperandAt(it.index(), replacement);
55            need_another_iteration |= value->IsPhi();
56          }
57        }
58      }
59      for (int i = 0; i < redundant_phis.length(); i++) {
60        block->RemovePhi(redundant_phis[i]);
61      }
62      redundant_phis.Clear();
63    }
64  } while (need_another_iteration);
65
66#if DEBUG
67  // Make sure that we *really* removed all redundant phis.
68  for (int i = 0; i < blocks->length(); ++i) {
69    for (int j = 0; j < blocks->at(i)->phis()->length(); j++) {
70      ASSERT(blocks->at(i)->phis()->at(j)->GetRedundantReplacement() == NULL);
71    }
72  }
73#endif
74}
75
76} }  // namespace v8::internal
77