OLD | NEW |
1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 13 matching lines...) Expand all Loading... |
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 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. | 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | 27 |
28 #include "hydrogen-redundant-phi.h" | 28 #include "hydrogen-redundant-phi.h" |
29 | 29 |
30 namespace v8 { | 30 namespace v8 { |
31 namespace internal { | 31 namespace internal { |
32 | 32 |
33 void HRedundantPhiEliminationPhase::Run() { | 33 void HRedundantPhiEliminationPhase::Run() { |
34 // We do a simple fixed point iteration without any work list, because | 34 // Gather all phis from all blocks first. |
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()); | 35 const ZoneList<HBasicBlock*>* blocks(graph()->blocks()); |
41 ZoneList<HPhi*> redundant_phis(blocks->length(), zone()); | 36 ZoneList<HPhi*> all_phis(blocks->length(), zone()); |
42 do { | 37 for (int i = 0; i < blocks->length(); ++i) { |
43 need_another_iteration = false; | 38 HBasicBlock* block = blocks->at(i); |
44 for (int i = 0; i < blocks->length(); ++i) { | 39 for (int j = 0; j < block->phis()->length(); j++) { |
45 HBasicBlock* block = blocks->at(i); | 40 all_phis.Add(block->phis()->at(j), zone()); |
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 } | 41 } |
64 } while (need_another_iteration); | 42 } |
| 43 |
| 44 // Iteratively reduce all phis in the list. |
| 45 ProcessPhis(&all_phis); |
65 | 46 |
66 #if DEBUG | 47 #if DEBUG |
67 // Make sure that we *really* removed all redundant phis. | 48 // Make sure that we *really* removed all redundant phis. |
68 for (int i = 0; i < blocks->length(); ++i) { | 49 for (int i = 0; i < blocks->length(); ++i) { |
69 for (int j = 0; j < blocks->at(i)->phis()->length(); j++) { | 50 for (int j = 0; j < blocks->at(i)->phis()->length(); j++) { |
70 ASSERT(blocks->at(i)->phis()->at(j)->GetRedundantReplacement() == NULL); | 51 ASSERT(blocks->at(i)->phis()->at(j)->GetRedundantReplacement() == NULL); |
71 } | 52 } |
72 } | 53 } |
73 #endif | 54 #endif |
74 } | 55 } |
75 | 56 |
| 57 |
| 58 void HRedundantPhiEliminationPhase::ProcessBlock(HBasicBlock* block) { |
| 59 ProcessPhis(block->phis()); |
| 60 } |
| 61 |
| 62 |
| 63 void 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 for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) { |
| 75 HValue* value = it.value(); |
| 76 value->SetOperandAt(it.index(), replacement); |
| 77 updated |= value->IsPhi(); // Iterate again if used in another phi. |
| 78 } |
| 79 phi->SetFlag(HValue::kIsDead); |
| 80 phi->block()->RemovePhi(phi); |
| 81 } |
| 82 } |
| 83 } while (updated); |
| 84 } |
| 85 |
| 86 |
76 } } // namespace v8::internal | 87 } } // namespace v8::internal |
OLD | NEW |