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 18 matching lines...) Expand all Loading... |
29 #define V8_HYDROGEN_GVN_H_ | 29 #define V8_HYDROGEN_GVN_H_ |
30 | 30 |
31 #include "hydrogen.h" | 31 #include "hydrogen.h" |
32 #include "hydrogen-instructions.h" | 32 #include "hydrogen-instructions.h" |
33 #include "compiler.h" | 33 #include "compiler.h" |
34 #include "zone.h" | 34 #include "zone.h" |
35 | 35 |
36 namespace v8 { | 36 namespace v8 { |
37 namespace internal { | 37 namespace internal { |
38 | 38 |
39 // Simple sparse set with O(1) add, contains, and clear. | |
40 class SparseSet { | |
41 public: | |
42 SparseSet(Zone* zone, int capacity) | |
43 : capacity_(capacity), | |
44 length_(0), | |
45 dense_(zone->NewArray<int>(capacity)), | |
46 sparse_(zone->NewArray<int>(capacity)) { | |
47 #ifndef NVALGRIND | |
48 // Initialize the sparse array to make valgrind happy. | |
49 memset(sparse_, 0, sizeof(sparse_[0]) * capacity); | |
50 #endif | |
51 } | |
52 | |
53 bool Contains(int n) const { | |
54 ASSERT(0 <= n && n < capacity_); | |
55 int d = sparse_[n]; | |
56 return 0 <= d && d < length_ && dense_[d] == n; | |
57 } | |
58 | |
59 bool Add(int n) { | |
60 if (Contains(n)) return false; | |
61 dense_[length_] = n; | |
62 sparse_[n] = length_; | |
63 ++length_; | |
64 return true; | |
65 } | |
66 | |
67 void Clear() { length_ = 0; } | |
68 | |
69 private: | |
70 int capacity_; | |
71 int length_; | |
72 int* dense_; | |
73 int* sparse_; | |
74 | |
75 DISALLOW_COPY_AND_ASSIGN(SparseSet); | |
76 }; | |
77 | |
78 | |
79 // Perform common subexpression elimination and loop-invariant code motion. | 39 // Perform common subexpression elimination and loop-invariant code motion. |
80 class HGlobalValueNumberingPhase : public HPhase { | 40 class HGlobalValueNumberingPhase : public HPhase { |
81 public: | 41 public: |
82 explicit HGlobalValueNumberingPhase(HGraph* graph); | 42 explicit HGlobalValueNumberingPhase(HGraph* graph); |
83 | 43 |
84 void Run() { | 44 void Run() { |
85 Analyze(); | 45 Analyze(); |
86 // Trigger a second analysis pass to further eliminate duplicate values | 46 // Trigger a second analysis pass to further eliminate duplicate values |
87 // that could only be discovered by removing side-effect-generating | 47 // that could only be discovered by removing side-effect-generating |
88 // instructions during the first pass. | 48 // instructions during the first pass. |
(...skipping 22 matching lines...) Expand all Loading... |
111 bool removed_side_effects_; | 71 bool removed_side_effects_; |
112 | 72 |
113 // A map of block IDs to their side effects. | 73 // A map of block IDs to their side effects. |
114 ZoneList<GVNFlagSet> block_side_effects_; | 74 ZoneList<GVNFlagSet> block_side_effects_; |
115 | 75 |
116 // A map of loop header block IDs to their loop's side effects. | 76 // A map of loop header block IDs to their loop's side effects. |
117 ZoneList<GVNFlagSet> loop_side_effects_; | 77 ZoneList<GVNFlagSet> loop_side_effects_; |
118 | 78 |
119 // Used when collecting side effects on paths from dominator to | 79 // Used when collecting side effects on paths from dominator to |
120 // dominated. | 80 // dominated. |
121 SparseSet visited_on_paths_; | 81 BitVector visited_on_paths_; |
122 | 82 |
123 DISALLOW_COPY_AND_ASSIGN(HGlobalValueNumberingPhase); | 83 DISALLOW_COPY_AND_ASSIGN(HGlobalValueNumberingPhase); |
124 }; | 84 }; |
125 | 85 |
126 | 86 |
127 } } // namespace v8::internal | 87 } } // namespace v8::internal |
128 | 88 |
129 #endif // V8_HYDROGEN_GVN_H_ | 89 #endif // V8_HYDROGEN_GVN_H_ |
OLD | NEW |