1b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Copyright 2013 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// found in the LICENSE file. 4b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 5b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifndef V8_EFFECTS_H_ 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define V8_EFFECTS_H_ 7b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 8f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch#include "src/ast/ast-types.h" 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 10b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace v8 { 11b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace internal { 12b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 13b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// A simple struct to represent (write) effects. A write is represented as a 15b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// modification of type bounds (e.g. of a variable). 16b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// 17b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// An effect can either be definite, if the write is known to have taken place, 18b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// or 'possible', if it was optional. The difference is relevant when composing 19b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// effects. 20b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// 21b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// There are two ways to compose effects: sequentially (they happen one after 22b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// the other) or alternatively (either one or the other happens). A definite 23b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// effect cancels out any previous effect upon sequencing. A possible effect 24b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// merges into a previous effect, i.e., type bounds are merged. Alternative 25b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// composition always merges bounds. It yields a possible effect if at least 26b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// one was only possible. 27b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochstruct Effect { 28b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch enum Modality { POSSIBLE, DEFINITE }; 29b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 30b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Modality modality; 31f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch AstBounds bounds; 32b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Effect() : modality(DEFINITE) {} 34f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch explicit Effect(AstBounds b, Modality m = DEFINITE) 35f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch : modality(m), bounds(b) {} 36b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 37b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // The unknown effect. 38b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static Effect Unknown(Zone* zone) { 39f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch return Effect(AstBounds::Unbounded(), POSSIBLE); 40b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 41b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 42b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static Effect Forget(Zone* zone) { 43f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch return Effect(AstBounds::Unbounded(), DEFINITE); 44b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 45b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 46b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Sequential composition, as in 'e1; e2'. 47b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static Effect Seq(Effect e1, Effect e2, Zone* zone) { 48b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (e2.modality == DEFINITE) return e2; 49f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch return Effect(AstBounds::Either(e1.bounds, e2.bounds, zone), e1.modality); 50b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 51b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 52b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Alternative composition, as in 'cond ? e1 : e2'. 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static Effect Alt(Effect e1, Effect e2, Zone* zone) { 54f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch return Effect(AstBounds::Either(e1.bounds, e2.bounds, zone), 55f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch e1.modality == POSSIBLE ? POSSIBLE : e2.modality); 56b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 57b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 58b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 59b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 60b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Classes encapsulating sets of effects on variables. 61b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// 62b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Effects maps variables to effects and supports sequential and alternative 63b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// composition. 64b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// 65b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// NestedEffects is an incremental representation that supports persistence 66b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// through functional extension. It represents the map as an adjoin of a list 67b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// of maps, whose tail can be shared. 68b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// 69b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Both classes provide similar interfaces, implemented in parts through the 70b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// EffectsMixin below (using sandwich style, to work around the style guide's 71b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// MI restriction). 72b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// 73b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// We also (ab)use Effects/NestedEffects as a representation for abstract 74b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// store typings. In that case, only definite effects are of interest. 75b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 76b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate<class Var, class Base, class Effects> 77b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass EffectsMixin: public Base { 78b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 79b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit EffectsMixin(Zone* zone) : Base(zone) {} 80b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 81b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Effect Lookup(Var var) { 82b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Locator locator; 83b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return this->Find(var, &locator) 84b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ? locator.value() : Effect::Unknown(Base::zone()); 85b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 86b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 87f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch AstBounds LookupBounds(Var var) { 88b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Effect effect = Lookup(var); 89f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch return effect.modality == Effect::DEFINITE ? effect.bounds 90f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch : AstBounds::Unbounded(); 91b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 92b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 93b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Sequential composition. 94b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Seq(Var var, Effect effect) { 95b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Locator locator; 96b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!this->Insert(var, &locator)) { 97b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch effect = Effect::Seq(locator.value(), effect, Base::zone()); 98b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 99b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch locator.set_value(effect); 100b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 101b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 102b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Seq(Effects that) { 103b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SeqMerger<EffectsMixin> merge = { *this }; 104b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch that.ForEach(&merge); 105b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 106b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 107b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Alternative composition. 108b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Alt(Var var, Effect effect) { 109b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Locator locator; 110b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!this->Insert(var, &locator)) { 111b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch effect = Effect::Alt(locator.value(), effect, Base::zone()); 112b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 113b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch locator.set_value(effect); 114b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 115b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Alt(Effects that) { 117b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AltWeakener<EffectsMixin> weaken = { *this, that }; 118b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch this->ForEach(&weaken); 119b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch AltMerger<EffectsMixin> merge = { *this }; 120b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch that.ForEach(&merge); 121b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 122b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 123b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Invalidation. 124b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Forget() { 125b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Overrider override = { 126b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Effect::Forget(Base::zone()), Effects(Base::zone()) }; 127b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch this->ForEach(&override); 128b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Seq(override.effects); 129b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 130b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 131b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch protected: 132b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch typedef typename Base::Locator Locator; 133b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 134b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch template<class Self> 135b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch struct SeqMerger { 136b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Call(Var var, Effect effect) { self.Seq(var, effect); } 137b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Self self; 138b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch }; 139b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 140b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch template<class Self> 141b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch struct AltMerger { 142b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Call(Var var, Effect effect) { self.Alt(var, effect); } 143b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Self self; 144b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch }; 145b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 146b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch template<class Self> 147b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch struct AltWeakener { 148b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Call(Var var, Effect effect) { 149b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (effect.modality == Effect::DEFINITE && !other.Contains(var)) { 150b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch effect.modality = Effect::POSSIBLE; 151b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Locator locator; 152b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch self.Insert(var, &locator); 153b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch locator.set_value(effect); 154b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 155b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 156b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Self self; 157b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Effects other; 158b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch }; 159b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 160b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch struct Overrider { 161b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Call(Var var, Effect effect) { effects.Seq(var, new_effect); } 162b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Effect new_effect; 163b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Effects effects; 164b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch }; 165b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 166b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 167b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 168b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate<class Var, Var kNoVar> class Effects; 169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate<class Var, Var kNoVar> class NestedEffectsBase; 170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate<class Var, Var kNoVar> 172b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass EffectsBase { 173b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit EffectsBase(Zone* zone) : map_(new(zone) Mapping(zone)) {} 175b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 176b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool IsEmpty() { return map_->is_empty(); } 177b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch protected: 179b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch friend class NestedEffectsBase<Var, kNoVar>; 180b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch friend class 181b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >; 182b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 183b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Zone* zone() { return map_->allocator().zone(); } 184b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 185b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch struct SplayTreeConfig { 186b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch typedef Var Key; 187b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch typedef Effect Value; 188b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static const Var kNoKey = kNoVar; 189b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static Effect NoValue() { return Effect(); } 190b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static int Compare(int x, int y) { return y - x; } 191b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch }; 192b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch typedef ZoneSplayTree<SplayTreeConfig> Mapping; 193b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch typedef typename Mapping::Locator Locator; 194b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 195b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool Contains(Var var) { 196b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(var != kNoVar); 197b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return map_->Contains(var); 198b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 199b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool Find(Var var, Locator* locator) { 200b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(var != kNoVar); 201b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return map_->Find(var, locator); 202b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 203b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool Insert(Var var, Locator* locator) { 204b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(var != kNoVar); 205b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return map_->Insert(var, locator); 206b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 207b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 208b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch template<class Callback> 209b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ForEach(Callback* callback) { 210b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return map_->ForEach(callback); 211b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 212b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 213b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 214b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Mapping* map_; 215b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 216b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 217b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate<class Var, Var kNoVar> 218b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochconst Var EffectsBase<Var, kNoVar>::SplayTreeConfig::kNoKey; 219b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 220b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate<class Var, Var kNoVar> 221b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass Effects: public 222b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EffectsMixin<Var, EffectsBase<Var, kNoVar>, Effects<Var, kNoVar> > { 223b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 224b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit Effects(Zone* zone) 225b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : EffectsMixin<Var, EffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >(zone) 226b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch {} 227b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 228b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 229b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 230b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate<class Var, Var kNoVar> 231b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass NestedEffectsBase { 232b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 233b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit NestedEffectsBase(Zone* zone) : node_(new(zone) Node(zone)) {} 234b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 235b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch template<class Callback> 236b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void ForEach(Callback* callback) { 237b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (node_->previous) NestedEffectsBase(node_->previous).ForEach(callback); 238b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch node_->effects.ForEach(callback); 239b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 240b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 241b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Effects<Var, kNoVar> Top() { return node_->effects; } 242b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 243b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool IsEmpty() { 244b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (Node* node = node_; node != NULL; node = node->previous) { 245b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!node->effects.IsEmpty()) return false; 246b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 247b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return true; 248b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 249b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 250b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch protected: 251b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch typedef typename EffectsBase<Var, kNoVar>::Locator Locator; 252b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 253b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Zone* zone() { return node_->zone; } 254b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 255b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void push() { node_ = new(node_->zone) Node(node_->zone, node_); } 256b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void pop() { node_ = node_->previous; } 257b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool is_empty() { return node_ == NULL; } 258b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 259b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool Contains(Var var) { 260b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(var != kNoVar); 261b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (Node* node = node_; node != NULL; node = node->previous) { 262b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (node->effects.Contains(var)) return true; 263b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 264b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return false; 265b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 266b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 267b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool Find(Var var, Locator* locator) { 268b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(var != kNoVar); 269b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (Node* node = node_; node != NULL; node = node->previous) { 270b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (node->effects.Find(var, locator)) return true; 271b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 272b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return false; 273b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 274b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 275b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool Insert(Var var, Locator* locator); 276b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 277b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 278b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch struct Node: ZoneObject { 279b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Zone* zone; 280b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Effects<Var, kNoVar> effects; 281b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Node* previous; 282b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit Node(Zone* zone, Node* previous = NULL) 283b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : zone(zone), effects(zone), previous(previous) {} 284b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch }; 285b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 286b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit NestedEffectsBase(Node* node) : node_(node) {} 287b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 288b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Node* node_; 289b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 290b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 291b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 292b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate<class Var, Var kNoVar> 293b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochbool NestedEffectsBase<Var, kNoVar>::Insert(Var var, Locator* locator) { 294b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(var != kNoVar); 295b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (!node_->effects.Insert(var, locator)) return false; 296b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Locator shadowed; 297b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (Node* node = node_->previous; node != NULL; node = node->previous) { 298b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (node->effects.Find(var, &shadowed)) { 299b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Initialize with shadowed entry. 300b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch locator->set_value(shadowed.value()); 301b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return false; 302b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 303b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 304b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return true; 305b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 306b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 307b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 308b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate<class Var, Var kNoVar> 309b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass NestedEffects: public 310b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> > { 311b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 312b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit NestedEffects(Zone* zone) : 313b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >( 314b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch zone) {} 315b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 316b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Create an extension of the current effect set. The current set should not 317b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // be modified while the extension is in use. 318b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch NestedEffects Push() { 319b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch NestedEffects result = *this; 320b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result.push(); 321b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return result; 322b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 323b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 324b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch NestedEffects Pop() { 325b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch NestedEffects result = *this; 326b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result.pop(); 327b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(!this->is_empty()); 328b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return result; 329b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 330b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 331b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 332014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace internal 333014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace v8 334b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 335b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif // V8_EFFECTS_H_ 336