danno@chromium.org | 5940060 | 2013-08-13 17:09:37 +0000 | [diff] [blame] | 1 | // Copyright 2013 the V8 project authors. All rights reserved. |
| 2 | // Redistribution and use in source and binary forms, with or without |
| 3 | // modification, are permitted provided that the following conditions are |
| 4 | // met: |
| 5 | // |
| 6 | // * Redistributions of source code must retain the above copyright |
| 7 | // notice, this list of conditions and the following disclaimer. |
| 8 | // * Redistributions in binary form must reproduce the above |
| 9 | // copyright notice, this list of conditions and the following |
| 10 | // disclaimer in the documentation and/or other materials provided |
| 11 | // with the distribution. |
| 12 | // * Neither the name of Google Inc. nor the names of its |
| 13 | // contributors may be used to endorse or promote products derived |
| 14 | // from this software without specific prior written permission. |
| 15 | // |
| 16 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 17 | // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 18 | // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 19 | // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 20 | // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 21 | // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 22 | // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 23 | // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 24 | // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 25 | // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 26 | // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 27 | |
| 28 | #ifndef V8_EFFECTS_H_ |
| 29 | #define V8_EFFECTS_H_ |
| 30 | |
| 31 | #include "v8.h" |
| 32 | |
| 33 | #include "types.h" |
| 34 | |
| 35 | namespace v8 { |
| 36 | namespace internal { |
| 37 | |
| 38 | |
| 39 | // A simple struct to represent (write) effects. A write is represented as a |
| 40 | // modification of type bounds (e.g. of a variable). |
| 41 | // |
| 42 | // An effect can either be definite, if the write is known to have taken place, |
| 43 | // or 'possible', if it was optional. The difference is relevant when composing |
| 44 | // effects. |
| 45 | // |
| 46 | // There are two ways to compose effects: sequentially (they happen one after |
| 47 | // the other) or alternatively (either one or the other happens). A definite |
| 48 | // effect cancels out any previous effect upon sequencing. A possible effect |
| 49 | // merges into a previous effect, i.e., type bounds are merged. Alternative |
| 50 | // composition always merges bounds. It yields a possible effect if at least |
| 51 | // one was only possible. |
| 52 | struct Effect { |
| 53 | enum Modality { POSSIBLE, DEFINITE }; |
| 54 | |
| 55 | Modality modality; |
| 56 | Bounds bounds; |
| 57 | |
verwaest@chromium.org | 32cb9b2 | 2013-08-21 11:18:12 +0000 | [diff] [blame] | 58 | Effect() : modality(DEFINITE) {} |
danno@chromium.org | 5940060 | 2013-08-13 17:09:37 +0000 | [diff] [blame] | 59 | Effect(Bounds b, Modality m = DEFINITE) : modality(m), bounds(b) {} |
| 60 | |
| 61 | // The unknown effect. |
| 62 | static Effect Unknown(Isolate* isolate) { |
| 63 | return Effect(Bounds::Unbounded(isolate), POSSIBLE); |
| 64 | } |
| 65 | |
| 66 | static Effect Forget(Isolate* isolate) { |
| 67 | return Effect(Bounds::Unbounded(isolate), DEFINITE); |
| 68 | } |
| 69 | |
| 70 | // Sequential composition, as in 'e1; e2'. |
| 71 | static Effect Seq(Effect e1, Effect e2, Isolate* isolate) { |
| 72 | if (e2.modality == DEFINITE) return e2; |
| 73 | return Effect(Bounds::Either(e1.bounds, e2.bounds, isolate), e1.modality); |
| 74 | } |
| 75 | |
| 76 | // Alternative composition, as in 'cond ? e1 : e2'. |
| 77 | static Effect Alt(Effect e1, Effect e2, Isolate* isolate) { |
| 78 | return Effect( |
| 79 | Bounds::Either(e1.bounds, e2.bounds, isolate), |
| 80 | e1.modality == POSSIBLE ? POSSIBLE : e2.modality); |
| 81 | } |
| 82 | }; |
| 83 | |
| 84 | |
| 85 | // Classes encapsulating sets of effects on variables. |
| 86 | // |
| 87 | // Effects maps variables to effects and supports sequential and alternative |
| 88 | // composition. |
| 89 | // |
| 90 | // NestedEffects is an incremental representation that supports persistence |
| 91 | // through functional extension. It represents the map as an adjoin of a list |
| 92 | // of maps, whose tail can be shared. |
| 93 | // |
| 94 | // Both classes provide similar interfaces, implemented in parts through the |
| 95 | // EffectsMixin below (using sandwich style, to work around the style guide's |
| 96 | // MI restriction). |
| 97 | // |
| 98 | // We also (ab)use Effects/NestedEffects as a representation for abstract |
| 99 | // store typings. In that case, only definite effects are of interest. |
| 100 | |
| 101 | template<class Var, class Base, class Effects> |
| 102 | class EffectsMixin: public Base { |
| 103 | public: |
| 104 | explicit EffectsMixin(Zone* zone) : Base(zone) {} |
| 105 | |
| 106 | Effect Lookup(Var var) { |
| 107 | Locator locator; |
| 108 | return this->Find(var, &locator) |
| 109 | ? locator.value() : Effect::Unknown(Base::isolate()); |
| 110 | } |
| 111 | |
| 112 | Bounds LookupBounds(Var var) { |
| 113 | Effect effect = Lookup(var); |
| 114 | return effect.modality == Effect::DEFINITE |
| 115 | ? effect.bounds : Bounds::Unbounded(Base::isolate()); |
| 116 | } |
| 117 | |
| 118 | // Sequential composition. |
| 119 | void Seq(Var var, Effect effect) { |
| 120 | Locator locator; |
| 121 | if (!this->Insert(var, &locator)) { |
| 122 | effect = Effect::Seq(locator.value(), effect, Base::isolate()); |
| 123 | } |
| 124 | locator.set_value(effect); |
| 125 | } |
| 126 | |
| 127 | void Seq(Effects that) { |
| 128 | SeqMerger<EffectsMixin> merge = { *this }; |
| 129 | that.ForEach(&merge); |
| 130 | } |
| 131 | |
| 132 | // Alternative composition. |
| 133 | void Alt(Var var, Effect effect) { |
| 134 | Locator locator; |
| 135 | if (!this->Insert(var, &locator)) { |
| 136 | effect = Effect::Alt(locator.value(), effect, Base::isolate()); |
| 137 | } |
| 138 | locator.set_value(effect); |
| 139 | } |
| 140 | |
| 141 | void Alt(Effects that) { |
| 142 | AltWeakener<EffectsMixin> weaken = { *this, that }; |
| 143 | this->ForEach(&weaken); |
| 144 | AltMerger<EffectsMixin> merge = { *this }; |
| 145 | that.ForEach(&merge); |
| 146 | } |
| 147 | |
| 148 | // Invalidation. |
| 149 | void Forget() { |
| 150 | Overrider override = { |
| 151 | Effect::Forget(Base::isolate()), Effects(Base::zone()) }; |
| 152 | this->ForEach(&override); |
| 153 | Seq(override.effects); |
| 154 | } |
| 155 | |
| 156 | protected: |
| 157 | typedef typename Base::Locator Locator; |
| 158 | |
| 159 | template<class Self> |
| 160 | struct SeqMerger { |
| 161 | void Call(Var var, Effect effect) { self.Seq(var, effect); } |
| 162 | Self self; |
| 163 | }; |
| 164 | |
| 165 | template<class Self> |
| 166 | struct AltMerger { |
| 167 | void Call(Var var, Effect effect) { self.Alt(var, effect); } |
| 168 | Self self; |
| 169 | }; |
| 170 | |
| 171 | template<class Self> |
| 172 | struct AltWeakener { |
| 173 | void Call(Var var, Effect effect) { |
| 174 | if (effect.modality == Effect::DEFINITE && !other.Contains(var)) { |
| 175 | effect.modality = Effect::POSSIBLE; |
| 176 | Locator locator; |
| 177 | self.Insert(var, &locator); |
| 178 | locator.set_value(effect); |
| 179 | } |
| 180 | } |
| 181 | Self self; |
| 182 | Effects other; |
| 183 | }; |
| 184 | |
| 185 | struct Overrider { |
| 186 | void Call(Var var, Effect effect) { effects.Seq(var, new_effect); } |
| 187 | Effect new_effect; |
| 188 | Effects effects; |
| 189 | }; |
| 190 | }; |
| 191 | |
| 192 | |
| 193 | template<class Var, Var kNoVar> class Effects; |
| 194 | template<class Var, Var kNoVar> class NestedEffectsBase; |
| 195 | |
| 196 | template<class Var, Var kNoVar> |
| 197 | class EffectsBase { |
| 198 | public: |
| 199 | explicit EffectsBase(Zone* zone) : map_(new(zone) Mapping(zone)) {} |
| 200 | |
| 201 | bool IsEmpty() { return map_->is_empty(); } |
| 202 | |
| 203 | protected: |
| 204 | friend class NestedEffectsBase<Var, kNoVar>; |
| 205 | friend class |
| 206 | EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >; |
| 207 | |
| 208 | Zone* zone() { return map_->allocator().zone(); } |
| 209 | Isolate* isolate() { return zone()->isolate(); } |
| 210 | |
| 211 | struct SplayTreeConfig { |
| 212 | typedef Var Key; |
| 213 | typedef Effect Value; |
| 214 | static const Var kNoKey = kNoVar; |
| 215 | static Effect NoValue() { return Effect(); } |
| 216 | static int Compare(int x, int y) { return y - x; } |
| 217 | }; |
| 218 | typedef ZoneSplayTree<SplayTreeConfig> Mapping; |
| 219 | typedef typename Mapping::Locator Locator; |
| 220 | |
| 221 | bool Contains(Var var) { |
| 222 | ASSERT(var != kNoVar); |
| 223 | return map_->Contains(var); |
| 224 | } |
| 225 | bool Find(Var var, Locator* locator) { |
| 226 | ASSERT(var != kNoVar); |
| 227 | return map_->Find(var, locator); |
| 228 | } |
| 229 | bool Insert(Var var, Locator* locator) { |
| 230 | ASSERT(var != kNoVar); |
| 231 | return map_->Insert(var, locator); |
| 232 | } |
| 233 | |
| 234 | template<class Callback> |
| 235 | void ForEach(Callback* callback) { |
| 236 | return map_->ForEach(callback); |
| 237 | } |
| 238 | |
| 239 | private: |
| 240 | Mapping* map_; |
| 241 | }; |
| 242 | |
| 243 | template<class Var, Var kNoVar> |
| 244 | const Var EffectsBase<Var, kNoVar>::SplayTreeConfig::kNoKey; |
| 245 | |
| 246 | template<class Var, Var kNoVar> |
| 247 | class Effects: public |
| 248 | EffectsMixin<Var, EffectsBase<Var, kNoVar>, Effects<Var, kNoVar> > { |
| 249 | public: |
| 250 | explicit Effects(Zone* zone) |
| 251 | : EffectsMixin<Var, EffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >(zone) |
| 252 | {} |
| 253 | }; |
| 254 | |
| 255 | |
| 256 | template<class Var, Var kNoVar> |
| 257 | class NestedEffectsBase { |
| 258 | public: |
| 259 | explicit NestedEffectsBase(Zone* zone) : node_(new(zone) Node(zone)) {} |
| 260 | |
| 261 | template<class Callback> |
| 262 | void ForEach(Callback* callback) { |
| 263 | if (node_->previous) NestedEffectsBase(node_->previous).ForEach(callback); |
| 264 | node_->effects.ForEach(callback); |
| 265 | } |
| 266 | |
| 267 | Effects<Var, kNoVar> Top() { return node_->effects; } |
| 268 | |
| 269 | bool IsEmpty() { |
| 270 | for (Node* node = node_; node != NULL; node = node->previous) { |
| 271 | if (!node->effects.IsEmpty()) return false; |
| 272 | } |
| 273 | return true; |
| 274 | } |
| 275 | |
| 276 | protected: |
| 277 | typedef typename EffectsBase<Var, kNoVar>::Locator Locator; |
| 278 | |
| 279 | Zone* zone() { return node_->zone; } |
| 280 | Isolate* isolate() { return zone()->isolate(); } |
| 281 | |
| 282 | void push() { node_ = new(node_->zone) Node(node_->zone, node_); } |
| 283 | void pop() { node_ = node_->previous; } |
| 284 | bool is_empty() { return node_ == NULL; } |
| 285 | |
| 286 | bool Contains(Var var) { |
| 287 | ASSERT(var != kNoVar); |
| 288 | for (Node* node = node_; node != NULL; node = node->previous) { |
| 289 | if (node->effects.Contains(var)) return true; |
| 290 | } |
| 291 | return false; |
| 292 | } |
| 293 | |
| 294 | bool Find(Var var, Locator* locator) { |
| 295 | ASSERT(var != kNoVar); |
| 296 | for (Node* node = node_; node != NULL; node = node->previous) { |
| 297 | if (node->effects.Find(var, locator)) return true; |
| 298 | } |
| 299 | return false; |
| 300 | } |
| 301 | |
| 302 | bool Insert(Var var, Locator* locator); |
| 303 | |
| 304 | private: |
| 305 | struct Node: ZoneObject { |
| 306 | Zone* zone; |
| 307 | Effects<Var, kNoVar> effects; |
| 308 | Node* previous; |
| 309 | explicit Node(Zone* zone, Node* previous = NULL) |
| 310 | : zone(zone), effects(zone), previous(previous) {} |
| 311 | }; |
| 312 | |
| 313 | explicit NestedEffectsBase(Node* node) : node_(node) {} |
| 314 | |
| 315 | Node* node_; |
| 316 | }; |
| 317 | |
| 318 | |
| 319 | template<class Var, Var kNoVar> |
| 320 | bool NestedEffectsBase<Var, kNoVar>::Insert(Var var, Locator* locator) { |
| 321 | ASSERT(var != kNoVar); |
| 322 | if (!node_->effects.Insert(var, locator)) return false; |
| 323 | Locator shadowed; |
| 324 | for (Node* node = node_->previous; node != NULL; node = node->previous) { |
| 325 | if (node->effects.Find(var, &shadowed)) { |
| 326 | // Initialize with shadowed entry. |
| 327 | locator->set_value(shadowed.value()); |
| 328 | return false; |
| 329 | } |
| 330 | } |
| 331 | return true; |
| 332 | } |
| 333 | |
| 334 | |
| 335 | template<class Var, Var kNoVar> |
| 336 | class NestedEffects: public |
| 337 | EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> > { |
| 338 | public: |
| 339 | explicit NestedEffects(Zone* zone) : |
| 340 | EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >( |
| 341 | zone) {} |
| 342 | |
| 343 | // Create an extension of the current effect set. The current set should not |
| 344 | // be modified while the extension is in use. |
| 345 | NestedEffects Push() { |
| 346 | NestedEffects result = *this; |
| 347 | result.push(); |
| 348 | return result; |
| 349 | } |
| 350 | |
| 351 | NestedEffects Pop() { |
| 352 | NestedEffects result = *this; |
| 353 | result.pop(); |
| 354 | ASSERT(!this->is_empty()); |
| 355 | return result; |
| 356 | } |
| 357 | }; |
| 358 | |
| 359 | } } // namespace v8::internal |
| 360 | |
| 361 | #endif // V8_EFFECTS_H_ |