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 58 Effect() {} 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_ 362