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/types.h" 9 10namespace v8 { 11namespace 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. 27struct 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) { 38 return Effect(Bounds::Unbounded(), POSSIBLE); 39 } 40 41 static Effect Forget(Zone* zone) { 42 return Effect(Bounds::Unbounded(), DEFINITE); 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 76template<class Var, class Base, class Effects> 77class 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 90 ? effect.bounds : Bounds::Unbounded(); 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 168template<class Var, Var kNoVar> class Effects; 169template<class Var, Var kNoVar> class NestedEffectsBase; 170 171template<class Var, Var kNoVar> 172class 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 217template<class Var, Var kNoVar> 218const Var EffectsBase<Var, kNoVar>::SplayTreeConfig::kNoKey; 219 220template<class Var, Var kNoVar> 221class 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 230template<class Var, Var kNoVar> 231class 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 292template<class Var, Var kNoVar> 293bool 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 308template<class Var, Var kNoVar> 309class 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 332} // namespace internal 333} // namespace v8 334 335#endif // V8_EFFECTS_H_ 336