src/v8/src/effects.h

   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() : modality(DEFINITE) {}
  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_