| 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 |