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 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
52 struct Effect { | 52 struct Effect { |
53 enum Modality { POSSIBLE, DEFINITE }; | 53 enum Modality { POSSIBLE, DEFINITE }; |
54 | 54 |
55 Modality modality; | 55 Modality modality; |
56 Bounds bounds; | 56 Bounds bounds; |
57 | 57 |
58 Effect() : modality(DEFINITE) {} | 58 Effect() : modality(DEFINITE) {} |
59 Effect(Bounds b, Modality m = DEFINITE) : modality(m), bounds(b) {} | 59 Effect(Bounds b, Modality m = DEFINITE) : modality(m), bounds(b) {} |
60 | 60 |
61 // The unknown effect. | 61 // The unknown effect. |
62 static Effect Unknown(Isolate* isolate) { | 62 static Effect Unknown(Zone* zone) { |
63 return Effect(Bounds::Unbounded(isolate), POSSIBLE); | 63 return Effect(Bounds::Unbounded(zone), POSSIBLE); |
64 } | 64 } |
65 | 65 |
66 static Effect Forget(Isolate* isolate) { | 66 static Effect Forget(Zone* zone) { |
67 return Effect(Bounds::Unbounded(isolate), DEFINITE); | 67 return Effect(Bounds::Unbounded(zone), DEFINITE); |
68 } | 68 } |
69 | 69 |
70 // Sequential composition, as in 'e1; e2'. | 70 // Sequential composition, as in 'e1; e2'. |
71 static Effect Seq(Effect e1, Effect e2, Isolate* isolate) { | 71 static Effect Seq(Effect e1, Effect e2, Zone* zone) { |
72 if (e2.modality == DEFINITE) return e2; | 72 if (e2.modality == DEFINITE) return e2; |
73 return Effect(Bounds::Either(e1.bounds, e2.bounds, isolate), e1.modality); | 73 return Effect(Bounds::Either(e1.bounds, e2.bounds, zone), e1.modality); |
74 } | 74 } |
75 | 75 |
76 // Alternative composition, as in 'cond ? e1 : e2'. | 76 // Alternative composition, as in 'cond ? e1 : e2'. |
77 static Effect Alt(Effect e1, Effect e2, Isolate* isolate) { | 77 static Effect Alt(Effect e1, Effect e2, Zone* zone) { |
78 return Effect( | 78 return Effect( |
79 Bounds::Either(e1.bounds, e2.bounds, isolate), | 79 Bounds::Either(e1.bounds, e2.bounds, zone), |
80 e1.modality == POSSIBLE ? POSSIBLE : e2.modality); | 80 e1.modality == POSSIBLE ? POSSIBLE : e2.modality); |
81 } | 81 } |
82 }; | 82 }; |
83 | 83 |
84 | 84 |
85 // Classes encapsulating sets of effects on variables. | 85 // Classes encapsulating sets of effects on variables. |
86 // | 86 // |
87 // Effects maps variables to effects and supports sequential and alternative | 87 // Effects maps variables to effects and supports sequential and alternative |
88 // composition. | 88 // composition. |
89 // | 89 // |
90 // NestedEffects is an incremental representation that supports persistence | 90 // NestedEffects is an incremental representation that supports persistence |
91 // through functional extension. It represents the map as an adjoin of a list | 91 // through functional extension. It represents the map as an adjoin of a list |
92 // of maps, whose tail can be shared. | 92 // of maps, whose tail can be shared. |
93 // | 93 // |
94 // Both classes provide similar interfaces, implemented in parts through the | 94 // Both classes provide similar interfaces, implemented in parts through the |
95 // EffectsMixin below (using sandwich style, to work around the style guide's | 95 // EffectsMixin below (using sandwich style, to work around the style guide's |
96 // MI restriction). | 96 // MI restriction). |
97 // | 97 // |
98 // We also (ab)use Effects/NestedEffects as a representation for abstract | 98 // We also (ab)use Effects/NestedEffects as a representation for abstract |
99 // store typings. In that case, only definite effects are of interest. | 99 // store typings. In that case, only definite effects are of interest. |
100 | 100 |
101 template<class Var, class Base, class Effects> | 101 template<class Var, class Base, class Effects> |
102 class EffectsMixin: public Base { | 102 class EffectsMixin: public Base { |
103 public: | 103 public: |
104 explicit EffectsMixin(Zone* zone) : Base(zone) {} | 104 explicit EffectsMixin(Zone* zone) : Base(zone) {} |
105 | 105 |
106 Effect Lookup(Var var) { | 106 Effect Lookup(Var var) { |
107 Locator locator; | 107 Locator locator; |
108 return this->Find(var, &locator) | 108 return this->Find(var, &locator) |
109 ? locator.value() : Effect::Unknown(Base::isolate()); | 109 ? locator.value() : Effect::Unknown(Base::zone()); |
110 } | 110 } |
111 | 111 |
112 Bounds LookupBounds(Var var) { | 112 Bounds LookupBounds(Var var) { |
113 Effect effect = Lookup(var); | 113 Effect effect = Lookup(var); |
114 return effect.modality == Effect::DEFINITE | 114 return effect.modality == Effect::DEFINITE |
115 ? effect.bounds : Bounds::Unbounded(Base::isolate()); | 115 ? effect.bounds : Bounds::Unbounded(Base::zone()); |
116 } | 116 } |
117 | 117 |
118 // Sequential composition. | 118 // Sequential composition. |
119 void Seq(Var var, Effect effect) { | 119 void Seq(Var var, Effect effect) { |
120 Locator locator; | 120 Locator locator; |
121 if (!this->Insert(var, &locator)) { | 121 if (!this->Insert(var, &locator)) { |
122 effect = Effect::Seq(locator.value(), effect, Base::isolate()); | 122 effect = Effect::Seq(locator.value(), effect, Base::zone()); |
123 } | 123 } |
124 locator.set_value(effect); | 124 locator.set_value(effect); |
125 } | 125 } |
126 | 126 |
127 void Seq(Effects that) { | 127 void Seq(Effects that) { |
128 SeqMerger<EffectsMixin> merge = { *this }; | 128 SeqMerger<EffectsMixin> merge = { *this }; |
129 that.ForEach(&merge); | 129 that.ForEach(&merge); |
130 } | 130 } |
131 | 131 |
132 // Alternative composition. | 132 // Alternative composition. |
133 void Alt(Var var, Effect effect) { | 133 void Alt(Var var, Effect effect) { |
134 Locator locator; | 134 Locator locator; |
135 if (!this->Insert(var, &locator)) { | 135 if (!this->Insert(var, &locator)) { |
136 effect = Effect::Alt(locator.value(), effect, Base::isolate()); | 136 effect = Effect::Alt(locator.value(), effect, Base::zone()); |
137 } | 137 } |
138 locator.set_value(effect); | 138 locator.set_value(effect); |
139 } | 139 } |
140 | 140 |
141 void Alt(Effects that) { | 141 void Alt(Effects that) { |
142 AltWeakener<EffectsMixin> weaken = { *this, that }; | 142 AltWeakener<EffectsMixin> weaken = { *this, that }; |
143 this->ForEach(&weaken); | 143 this->ForEach(&weaken); |
144 AltMerger<EffectsMixin> merge = { *this }; | 144 AltMerger<EffectsMixin> merge = { *this }; |
145 that.ForEach(&merge); | 145 that.ForEach(&merge); |
146 } | 146 } |
147 | 147 |
148 // Invalidation. | 148 // Invalidation. |
149 void Forget() { | 149 void Forget() { |
150 Overrider override = { | 150 Overrider override = { |
151 Effect::Forget(Base::isolate()), Effects(Base::zone()) }; | 151 Effect::Forget(Base::zone()), Effects(Base::zone()) }; |
152 this->ForEach(&override); | 152 this->ForEach(&override); |
153 Seq(override.effects); | 153 Seq(override.effects); |
154 } | 154 } |
155 | 155 |
156 protected: | 156 protected: |
157 typedef typename Base::Locator Locator; | 157 typedef typename Base::Locator Locator; |
158 | 158 |
159 template<class Self> | 159 template<class Self> |
160 struct SeqMerger { | 160 struct SeqMerger { |
161 void Call(Var var, Effect effect) { self.Seq(var, effect); } | 161 void Call(Var var, Effect effect) { self.Seq(var, effect); } |
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
199 explicit EffectsBase(Zone* zone) : map_(new(zone) Mapping(zone)) {} | 199 explicit EffectsBase(Zone* zone) : map_(new(zone) Mapping(zone)) {} |
200 | 200 |
201 bool IsEmpty() { return map_->is_empty(); } | 201 bool IsEmpty() { return map_->is_empty(); } |
202 | 202 |
203 protected: | 203 protected: |
204 friend class NestedEffectsBase<Var, kNoVar>; | 204 friend class NestedEffectsBase<Var, kNoVar>; |
205 friend class | 205 friend class |
206 EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >; | 206 EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >; |
207 | 207 |
208 Zone* zone() { return map_->allocator().zone(); } | 208 Zone* zone() { return map_->allocator().zone(); } |
209 Isolate* isolate() { return zone()->isolate(); } | |
210 | 209 |
211 struct SplayTreeConfig { | 210 struct SplayTreeConfig { |
212 typedef Var Key; | 211 typedef Var Key; |
213 typedef Effect Value; | 212 typedef Effect Value; |
214 static const Var kNoKey = kNoVar; | 213 static const Var kNoKey = kNoVar; |
215 static Effect NoValue() { return Effect(); } | 214 static Effect NoValue() { return Effect(); } |
216 static int Compare(int x, int y) { return y - x; } | 215 static int Compare(int x, int y) { return y - x; } |
217 }; | 216 }; |
218 typedef ZoneSplayTree<SplayTreeConfig> Mapping; | 217 typedef ZoneSplayTree<SplayTreeConfig> Mapping; |
219 typedef typename Mapping::Locator Locator; | 218 typedef typename Mapping::Locator Locator; |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
270 for (Node* node = node_; node != NULL; node = node->previous) { | 269 for (Node* node = node_; node != NULL; node = node->previous) { |
271 if (!node->effects.IsEmpty()) return false; | 270 if (!node->effects.IsEmpty()) return false; |
272 } | 271 } |
273 return true; | 272 return true; |
274 } | 273 } |
275 | 274 |
276 protected: | 275 protected: |
277 typedef typename EffectsBase<Var, kNoVar>::Locator Locator; | 276 typedef typename EffectsBase<Var, kNoVar>::Locator Locator; |
278 | 277 |
279 Zone* zone() { return node_->zone; } | 278 Zone* zone() { return node_->zone; } |
280 Isolate* isolate() { return zone()->isolate(); } | |
281 | 279 |
282 void push() { node_ = new(node_->zone) Node(node_->zone, node_); } | 280 void push() { node_ = new(node_->zone) Node(node_->zone, node_); } |
283 void pop() { node_ = node_->previous; } | 281 void pop() { node_ = node_->previous; } |
284 bool is_empty() { return node_ == NULL; } | 282 bool is_empty() { return node_ == NULL; } |
285 | 283 |
286 bool Contains(Var var) { | 284 bool Contains(Var var) { |
287 ASSERT(var != kNoVar); | 285 ASSERT(var != kNoVar); |
288 for (Node* node = node_; node != NULL; node = node->previous) { | 286 for (Node* node = node_; node != NULL; node = node->previous) { |
289 if (node->effects.Contains(var)) return true; | 287 if (node->effects.Contains(var)) return true; |
290 } | 288 } |
(...skipping 61 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
352 NestedEffects result = *this; | 350 NestedEffects result = *this; |
353 result.pop(); | 351 result.pop(); |
354 ASSERT(!this->is_empty()); | 352 ASSERT(!this->is_empty()); |
355 return result; | 353 return result; |
356 } | 354 } |
357 }; | 355 }; |
358 | 356 |
359 } } // namespace v8::internal | 357 } } // namespace v8::internal |
360 | 358 |
361 #endif // V8_EFFECTS_H_ | 359 #endif // V8_EFFECTS_H_ |
OLD | NEW |