Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1 | // Copyright 2013 the V8 project authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | |
| 5 | #ifndef V8_EFFECTS_H_ |
| 6 | #define V8_EFFECTS_H_ |
| 7 | |
| 8 | #include "src/v8.h" |
| 9 | |
| 10 | #include "src/types.h" |
| 11 | |
| 12 | namespace v8 { |
| 13 | namespace internal { |
| 14 | |
| 15 | |
| 16 | // A simple struct to represent (write) effects. A write is represented as a |
| 17 | // modification of type bounds (e.g. of a variable). |
| 18 | // |
| 19 | // An effect can either be definite, if the write is known to have taken place, |
| 20 | // or 'possible', if it was optional. The difference is relevant when composing |
| 21 | // effects. |
| 22 | // |
| 23 | // There are two ways to compose effects: sequentially (they happen one after |
| 24 | // the other) or alternatively (either one or the other happens). A definite |
| 25 | // effect cancels out any previous effect upon sequencing. A possible effect |
| 26 | // merges into a previous effect, i.e., type bounds are merged. Alternative |
| 27 | // composition always merges bounds. It yields a possible effect if at least |
| 28 | // one was only possible. |
| 29 | struct Effect { |
| 30 | enum Modality { POSSIBLE, DEFINITE }; |
| 31 | |
| 32 | Modality modality; |
| 33 | Bounds bounds; |
| 34 | |
| 35 | Effect() : modality(DEFINITE) {} |
| 36 | explicit Effect(Bounds b, Modality m = DEFINITE) : modality(m), bounds(b) {} |
| 37 | |
| 38 | // The unknown effect. |
| 39 | static Effect Unknown(Zone* zone) { |
| 40 | return Effect(Bounds::Unbounded(zone), POSSIBLE); |
| 41 | } |
| 42 | |
| 43 | static Effect Forget(Zone* zone) { |
| 44 | return Effect(Bounds::Unbounded(zone), DEFINITE); |
| 45 | } |
| 46 | |
| 47 | // Sequential composition, as in 'e1; e2'. |
| 48 | static Effect Seq(Effect e1, Effect e2, Zone* zone) { |
| 49 | if (e2.modality == DEFINITE) return e2; |
| 50 | return Effect(Bounds::Either(e1.bounds, e2.bounds, zone), e1.modality); |
| 51 | } |
| 52 | |
| 53 | // Alternative composition, as in 'cond ? e1 : e2'. |
| 54 | static Effect Alt(Effect e1, Effect e2, Zone* zone) { |
| 55 | return Effect( |
| 56 | Bounds::Either(e1.bounds, e2.bounds, zone), |
| 57 | e1.modality == POSSIBLE ? POSSIBLE : e2.modality); |
| 58 | } |
| 59 | }; |
| 60 | |
| 61 | |
| 62 | // Classes encapsulating sets of effects on variables. |
| 63 | // |
| 64 | // Effects maps variables to effects and supports sequential and alternative |
| 65 | // composition. |
| 66 | // |
| 67 | // NestedEffects is an incremental representation that supports persistence |
| 68 | // through functional extension. It represents the map as an adjoin of a list |
| 69 | // of maps, whose tail can be shared. |
| 70 | // |
| 71 | // Both classes provide similar interfaces, implemented in parts through the |
| 72 | // EffectsMixin below (using sandwich style, to work around the style guide's |
| 73 | // MI restriction). |
| 74 | // |
| 75 | // We also (ab)use Effects/NestedEffects as a representation for abstract |
| 76 | // store typings. In that case, only definite effects are of interest. |
| 77 | |
| 78 | template<class Var, class Base, class Effects> |
| 79 | class EffectsMixin: public Base { |
| 80 | public: |
| 81 | explicit EffectsMixin(Zone* zone) : Base(zone) {} |
| 82 | |
| 83 | Effect Lookup(Var var) { |
| 84 | Locator locator; |
| 85 | return this->Find(var, &locator) |
| 86 | ? locator.value() : Effect::Unknown(Base::zone()); |
| 87 | } |
| 88 | |
| 89 | Bounds LookupBounds(Var var) { |
| 90 | Effect effect = Lookup(var); |
| 91 | return effect.modality == Effect::DEFINITE |
| 92 | ? effect.bounds : Bounds::Unbounded(Base::zone()); |
| 93 | } |
| 94 | |
| 95 | // Sequential composition. |
| 96 | void Seq(Var var, Effect effect) { |
| 97 | Locator locator; |
| 98 | if (!this->Insert(var, &locator)) { |
| 99 | effect = Effect::Seq(locator.value(), effect, Base::zone()); |
| 100 | } |
| 101 | locator.set_value(effect); |
| 102 | } |
| 103 | |
| 104 | void Seq(Effects that) { |
| 105 | SeqMerger<EffectsMixin> merge = { *this }; |
| 106 | that.ForEach(&merge); |
| 107 | } |
| 108 | |
| 109 | // Alternative composition. |
| 110 | void Alt(Var var, Effect effect) { |
| 111 | Locator locator; |
| 112 | if (!this->Insert(var, &locator)) { |
| 113 | effect = Effect::Alt(locator.value(), effect, Base::zone()); |
| 114 | } |
| 115 | locator.set_value(effect); |
| 116 | } |
| 117 | |
| 118 | void Alt(Effects that) { |
| 119 | AltWeakener<EffectsMixin> weaken = { *this, that }; |
| 120 | this->ForEach(&weaken); |
| 121 | AltMerger<EffectsMixin> merge = { *this }; |
| 122 | that.ForEach(&merge); |
| 123 | } |
| 124 | |
| 125 | // Invalidation. |
| 126 | void Forget() { |
| 127 | Overrider override = { |
| 128 | Effect::Forget(Base::zone()), Effects(Base::zone()) }; |
| 129 | this->ForEach(&override); |
| 130 | Seq(override.effects); |
| 131 | } |
| 132 | |
| 133 | protected: |
| 134 | typedef typename Base::Locator Locator; |
| 135 | |
| 136 | template<class Self> |
| 137 | struct SeqMerger { |
| 138 | void Call(Var var, Effect effect) { self.Seq(var, effect); } |
| 139 | Self self; |
| 140 | }; |
| 141 | |
| 142 | template<class Self> |
| 143 | struct AltMerger { |
| 144 | void Call(Var var, Effect effect) { self.Alt(var, effect); } |
| 145 | Self self; |
| 146 | }; |
| 147 | |
| 148 | template<class Self> |
| 149 | struct AltWeakener { |
| 150 | void Call(Var var, Effect effect) { |
| 151 | if (effect.modality == Effect::DEFINITE && !other.Contains(var)) { |
| 152 | effect.modality = Effect::POSSIBLE; |
| 153 | Locator locator; |
| 154 | self.Insert(var, &locator); |
| 155 | locator.set_value(effect); |
| 156 | } |
| 157 | } |
| 158 | Self self; |
| 159 | Effects other; |
| 160 | }; |
| 161 | |
| 162 | struct Overrider { |
| 163 | void Call(Var var, Effect effect) { effects.Seq(var, new_effect); } |
| 164 | Effect new_effect; |
| 165 | Effects effects; |
| 166 | }; |
| 167 | }; |
| 168 | |
| 169 | |
| 170 | template<class Var, Var kNoVar> class Effects; |
| 171 | template<class Var, Var kNoVar> class NestedEffectsBase; |
| 172 | |
| 173 | template<class Var, Var kNoVar> |
| 174 | class EffectsBase { |
| 175 | public: |
| 176 | explicit EffectsBase(Zone* zone) : map_(new(zone) Mapping(zone)) {} |
| 177 | |
| 178 | bool IsEmpty() { return map_->is_empty(); } |
| 179 | |
| 180 | protected: |
| 181 | friend class NestedEffectsBase<Var, kNoVar>; |
| 182 | friend class |
| 183 | EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >; |
| 184 | |
| 185 | Zone* zone() { return map_->allocator().zone(); } |
| 186 | |
| 187 | struct SplayTreeConfig { |
| 188 | typedef Var Key; |
| 189 | typedef Effect Value; |
| 190 | static const Var kNoKey = kNoVar; |
| 191 | static Effect NoValue() { return Effect(); } |
| 192 | static int Compare(int x, int y) { return y - x; } |
| 193 | }; |
| 194 | typedef ZoneSplayTree<SplayTreeConfig> Mapping; |
| 195 | typedef typename Mapping::Locator Locator; |
| 196 | |
| 197 | bool Contains(Var var) { |
| 198 | DCHECK(var != kNoVar); |
| 199 | return map_->Contains(var); |
| 200 | } |
| 201 | bool Find(Var var, Locator* locator) { |
| 202 | DCHECK(var != kNoVar); |
| 203 | return map_->Find(var, locator); |
| 204 | } |
| 205 | bool Insert(Var var, Locator* locator) { |
| 206 | DCHECK(var != kNoVar); |
| 207 | return map_->Insert(var, locator); |
| 208 | } |
| 209 | |
| 210 | template<class Callback> |
| 211 | void ForEach(Callback* callback) { |
| 212 | return map_->ForEach(callback); |
| 213 | } |
| 214 | |
| 215 | private: |
| 216 | Mapping* map_; |
| 217 | }; |
| 218 | |
| 219 | template<class Var, Var kNoVar> |
| 220 | const Var EffectsBase<Var, kNoVar>::SplayTreeConfig::kNoKey; |
| 221 | |
| 222 | template<class Var, Var kNoVar> |
| 223 | class Effects: public |
| 224 | EffectsMixin<Var, EffectsBase<Var, kNoVar>, Effects<Var, kNoVar> > { |
| 225 | public: |
| 226 | explicit Effects(Zone* zone) |
| 227 | : EffectsMixin<Var, EffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >(zone) |
| 228 | {} |
| 229 | }; |
| 230 | |
| 231 | |
| 232 | template<class Var, Var kNoVar> |
| 233 | class NestedEffectsBase { |
| 234 | public: |
| 235 | explicit NestedEffectsBase(Zone* zone) : node_(new(zone) Node(zone)) {} |
| 236 | |
| 237 | template<class Callback> |
| 238 | void ForEach(Callback* callback) { |
| 239 | if (node_->previous) NestedEffectsBase(node_->previous).ForEach(callback); |
| 240 | node_->effects.ForEach(callback); |
| 241 | } |
| 242 | |
| 243 | Effects<Var, kNoVar> Top() { return node_->effects; } |
| 244 | |
| 245 | bool IsEmpty() { |
| 246 | for (Node* node = node_; node != NULL; node = node->previous) { |
| 247 | if (!node->effects.IsEmpty()) return false; |
| 248 | } |
| 249 | return true; |
| 250 | } |
| 251 | |
| 252 | protected: |
| 253 | typedef typename EffectsBase<Var, kNoVar>::Locator Locator; |
| 254 | |
| 255 | Zone* zone() { return node_->zone; } |
| 256 | |
| 257 | void push() { node_ = new(node_->zone) Node(node_->zone, node_); } |
| 258 | void pop() { node_ = node_->previous; } |
| 259 | bool is_empty() { return node_ == NULL; } |
| 260 | |
| 261 | bool Contains(Var var) { |
| 262 | DCHECK(var != kNoVar); |
| 263 | for (Node* node = node_; node != NULL; node = node->previous) { |
| 264 | if (node->effects.Contains(var)) return true; |
| 265 | } |
| 266 | return false; |
| 267 | } |
| 268 | |
| 269 | bool Find(Var var, Locator* locator) { |
| 270 | DCHECK(var != kNoVar); |
| 271 | for (Node* node = node_; node != NULL; node = node->previous) { |
| 272 | if (node->effects.Find(var, locator)) return true; |
| 273 | } |
| 274 | return false; |
| 275 | } |
| 276 | |
| 277 | bool Insert(Var var, Locator* locator); |
| 278 | |
| 279 | private: |
| 280 | struct Node: ZoneObject { |
| 281 | Zone* zone; |
| 282 | Effects<Var, kNoVar> effects; |
| 283 | Node* previous; |
| 284 | explicit Node(Zone* zone, Node* previous = NULL) |
| 285 | : zone(zone), effects(zone), previous(previous) {} |
| 286 | }; |
| 287 | |
| 288 | explicit NestedEffectsBase(Node* node) : node_(node) {} |
| 289 | |
| 290 | Node* node_; |
| 291 | }; |
| 292 | |
| 293 | |
| 294 | template<class Var, Var kNoVar> |
| 295 | bool NestedEffectsBase<Var, kNoVar>::Insert(Var var, Locator* locator) { |
| 296 | DCHECK(var != kNoVar); |
| 297 | if (!node_->effects.Insert(var, locator)) return false; |
| 298 | Locator shadowed; |
| 299 | for (Node* node = node_->previous; node != NULL; node = node->previous) { |
| 300 | if (node->effects.Find(var, &shadowed)) { |
| 301 | // Initialize with shadowed entry. |
| 302 | locator->set_value(shadowed.value()); |
| 303 | return false; |
| 304 | } |
| 305 | } |
| 306 | return true; |
| 307 | } |
| 308 | |
| 309 | |
| 310 | template<class Var, Var kNoVar> |
| 311 | class NestedEffects: public |
| 312 | EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> > { |
| 313 | public: |
| 314 | explicit NestedEffects(Zone* zone) : |
| 315 | EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >( |
| 316 | zone) {} |
| 317 | |
| 318 | // Create an extension of the current effect set. The current set should not |
| 319 | // be modified while the extension is in use. |
| 320 | NestedEffects Push() { |
| 321 | NestedEffects result = *this; |
| 322 | result.push(); |
| 323 | return result; |
| 324 | } |
| 325 | |
| 326 | NestedEffects Pop() { |
| 327 | NestedEffects result = *this; |
| 328 | result.pop(); |
| 329 | DCHECK(!this->is_empty()); |
| 330 | return result; |
| 331 | } |
| 332 | }; |
| 333 | |
| 334 | } } // namespace v8::internal |
| 335 | |
| 336 | #endif // V8_EFFECTS_H_ |