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 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 ASSERT(var != kNoVar); 199 return map_->Contains(var); 200 } 201 bool Find(Var var, Locator* locator) { 202 ASSERT(var != kNoVar); 203 return map_->Find(var, locator); 204 } 205 bool Insert(Var var, Locator* locator) { 206 ASSERT(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 ASSERT(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 ASSERT(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 ASSERT(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 ASSERT(!this->is_empty()); 330 return result; 331 } 332 }; 333 334 } } // namespace v8::internal 335 336 #endif // V8_EFFECTS_H_ 337