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