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