1594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// Copyright 2013 the V8 project authors. All rights reserved. 2594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// Redistribution and use in source and binary forms, with or without 3594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// modification, are permitted provided that the following conditions are 4594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// met: 5594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// 6594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// * Redistributions of source code must retain the above copyright 7594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// notice, this list of conditions and the following disclaimer. 8594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// * Redistributions in binary form must reproduce the above 9594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// copyright notice, this list of conditions and the following 10594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// disclaimer in the documentation and/or other materials provided 11594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// with the distribution. 12594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// * Neither the name of Google Inc. nor the names of its 13594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// contributors may be used to endorse or promote products derived 14594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// from this software without specific prior written permission. 15594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// 16594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 28594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org#ifndef V8_EFFECTS_H_ 29594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org#define V8_EFFECTS_H_ 30594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 31594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org#include "v8.h" 32594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 33594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org#include "types.h" 34594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 35594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgnamespace v8 { 36594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgnamespace internal { 37594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 38594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 39594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// A simple struct to represent (write) effects. A write is represented as a 40594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// modification of type bounds (e.g. of a variable). 41594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// 42594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// An effect can either be definite, if the write is known to have taken place, 43594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// or 'possible', if it was optional. The difference is relevant when composing 44594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// effects. 45594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// 46594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// There are two ways to compose effects: sequentially (they happen one after 47594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// the other) or alternatively (either one or the other happens). A definite 48594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// effect cancels out any previous effect upon sequencing. A possible effect 49594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// merges into a previous effect, i.e., type bounds are merged. Alternative 50594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// composition always merges bounds. It yields a possible effect if at least 51594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// one was only possible. 52594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgstruct Effect { 53594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org enum Modality { POSSIBLE, DEFINITE }; 54594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 55594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Modality modality; 56594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Bounds bounds; 57594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 58594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Effect() {} 59594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Effect(Bounds b, Modality m = DEFINITE) : modality(m), bounds(b) {} 60594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 61594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // The unknown effect. 62594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org static Effect Unknown(Isolate* isolate) { 63594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return Effect(Bounds::Unbounded(isolate), POSSIBLE); 64594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 65594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 66594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org static Effect Forget(Isolate* isolate) { 67594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return Effect(Bounds::Unbounded(isolate), DEFINITE); 68594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 69594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 70594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Sequential composition, as in 'e1; e2'. 71594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org static Effect Seq(Effect e1, Effect e2, Isolate* isolate) { 72594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (e2.modality == DEFINITE) return e2; 73594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return Effect(Bounds::Either(e1.bounds, e2.bounds, isolate), e1.modality); 74594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 75594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 76594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Alternative composition, as in 'cond ? e1 : e2'. 77594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org static Effect Alt(Effect e1, Effect e2, Isolate* isolate) { 78594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return Effect( 79594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Bounds::Either(e1.bounds, e2.bounds, isolate), 80594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org e1.modality == POSSIBLE ? POSSIBLE : e2.modality); 81594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 82594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org}; 83594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 84594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 85594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// Classes encapsulating sets of effects on variables. 86594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// 87594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// Effects maps variables to effects and supports sequential and alternative 88594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// composition. 89594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// 90594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// NestedEffects is an incremental representation that supports persistence 91594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// through functional extension. It represents the map as an adjoin of a list 92594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// of maps, whose tail can be shared. 93594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// 94594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// Both classes provide similar interfaces, implemented in parts through the 95594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// EffectsMixin below (using sandwich style, to work around the style guide's 96594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// MI restriction). 97594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// 98594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// We also (ab)use Effects/NestedEffects as a representation for abstract 99594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org// store typings. In that case, only definite effects are of interest. 100594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 101594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgtemplate<class Var, class Base, class Effects> 102594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgclass EffectsMixin: public Base { 103594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org public: 104594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org explicit EffectsMixin(Zone* zone) : Base(zone) {} 105594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 106594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Effect Lookup(Var var) { 107594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Locator locator; 108594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return this->Find(var, &locator) 109594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org ? locator.value() : Effect::Unknown(Base::isolate()); 110594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 111594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 112594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Bounds LookupBounds(Var var) { 113594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Effect effect = Lookup(var); 114594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return effect.modality == Effect::DEFINITE 115594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org ? effect.bounds : Bounds::Unbounded(Base::isolate()); 116594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 117594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 118594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Sequential composition. 119594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org void Seq(Var var, Effect effect) { 120594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Locator locator; 121594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (!this->Insert(var, &locator)) { 122594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org effect = Effect::Seq(locator.value(), effect, Base::isolate()); 123594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 124594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org locator.set_value(effect); 125594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 126594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 127594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org void Seq(Effects that) { 128594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org SeqMerger<EffectsMixin> merge = { *this }; 129594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org that.ForEach(&merge); 130594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 131594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 132594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Alternative composition. 133594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org void Alt(Var var, Effect effect) { 134594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Locator locator; 135594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (!this->Insert(var, &locator)) { 136594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org effect = Effect::Alt(locator.value(), effect, Base::isolate()); 137594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 138594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org locator.set_value(effect); 139594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 140594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 141594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org void Alt(Effects that) { 142594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org AltWeakener<EffectsMixin> weaken = { *this, that }; 143594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org this->ForEach(&weaken); 144594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org AltMerger<EffectsMixin> merge = { *this }; 145594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org that.ForEach(&merge); 146594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 147594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 148594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Invalidation. 149594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org void Forget() { 150594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Overrider override = { 151594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Effect::Forget(Base::isolate()), Effects(Base::zone()) }; 152594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org this->ForEach(&override); 153594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Seq(override.effects); 154594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 155594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 156594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org protected: 157594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org typedef typename Base::Locator Locator; 158594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 159594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org template<class Self> 160594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org struct SeqMerger { 161594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org void Call(Var var, Effect effect) { self.Seq(var, effect); } 162594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Self self; 163594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org }; 164594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 165594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org template<class Self> 166594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org struct AltMerger { 167594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org void Call(Var var, Effect effect) { self.Alt(var, effect); } 168594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Self self; 169594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org }; 170594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 171594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org template<class Self> 172594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org struct AltWeakener { 173594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org void Call(Var var, Effect effect) { 174594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (effect.modality == Effect::DEFINITE && !other.Contains(var)) { 175594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org effect.modality = Effect::POSSIBLE; 176594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Locator locator; 177594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org self.Insert(var, &locator); 178594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org locator.set_value(effect); 179594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 180594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 181594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Self self; 182594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Effects other; 183594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org }; 184594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 185594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org struct Overrider { 186594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org void Call(Var var, Effect effect) { effects.Seq(var, new_effect); } 187594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Effect new_effect; 188594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Effects effects; 189594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org }; 190594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org}; 191594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 192594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 193594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgtemplate<class Var, Var kNoVar> class Effects; 194594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgtemplate<class Var, Var kNoVar> class NestedEffectsBase; 195594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 196594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgtemplate<class Var, Var kNoVar> 197594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgclass EffectsBase { 198594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org public: 199594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org explicit EffectsBase(Zone* zone) : map_(new(zone) Mapping(zone)) {} 200594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 201594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org bool IsEmpty() { return map_->is_empty(); } 202594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 203594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org protected: 204594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org friend class NestedEffectsBase<Var, kNoVar>; 205594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org friend class 206594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >; 207594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 208594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Zone* zone() { return map_->allocator().zone(); } 209594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Isolate* isolate() { return zone()->isolate(); } 210594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 211594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org struct SplayTreeConfig { 212594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org typedef Var Key; 213594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org typedef Effect Value; 214594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org static const Var kNoKey = kNoVar; 215594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org static Effect NoValue() { return Effect(); } 216594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org static int Compare(int x, int y) { return y - x; } 217594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org }; 218594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org typedef ZoneSplayTree<SplayTreeConfig> Mapping; 219594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org typedef typename Mapping::Locator Locator; 220594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 221594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org bool Contains(Var var) { 222594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org ASSERT(var != kNoVar); 223594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return map_->Contains(var); 224594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 225594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org bool Find(Var var, Locator* locator) { 226594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org ASSERT(var != kNoVar); 227594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return map_->Find(var, locator); 228594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 229594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org bool Insert(Var var, Locator* locator) { 230594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org ASSERT(var != kNoVar); 231594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return map_->Insert(var, locator); 232594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 233594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 234594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org template<class Callback> 235594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org void ForEach(Callback* callback) { 236594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return map_->ForEach(callback); 237594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 238594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 239594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org private: 240594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Mapping* map_; 241594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org}; 242594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 243594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgtemplate<class Var, Var kNoVar> 244594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgconst Var EffectsBase<Var, kNoVar>::SplayTreeConfig::kNoKey; 245594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 246594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgtemplate<class Var, Var kNoVar> 247594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgclass Effects: public 248594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org EffectsMixin<Var, EffectsBase<Var, kNoVar>, Effects<Var, kNoVar> > { 249594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org public: 250594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org explicit Effects(Zone* zone) 251594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org : EffectsMixin<Var, EffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >(zone) 252594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org {} 253594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org}; 254594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 255594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 256594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgtemplate<class Var, Var kNoVar> 257594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgclass NestedEffectsBase { 258594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org public: 259594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org explicit NestedEffectsBase(Zone* zone) : node_(new(zone) Node(zone)) {} 260594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 261594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org template<class Callback> 262594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org void ForEach(Callback* callback) { 263594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (node_->previous) NestedEffectsBase(node_->previous).ForEach(callback); 264594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org node_->effects.ForEach(callback); 265594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 266594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 267594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Effects<Var, kNoVar> Top() { return node_->effects; } 268594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 269594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org bool IsEmpty() { 270594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org for (Node* node = node_; node != NULL; node = node->previous) { 271594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (!node->effects.IsEmpty()) return false; 272594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 273594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return true; 274594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 275594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 276594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org protected: 277594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org typedef typename EffectsBase<Var, kNoVar>::Locator Locator; 278594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 279594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Zone* zone() { return node_->zone; } 280594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Isolate* isolate() { return zone()->isolate(); } 281594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 282594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org void push() { node_ = new(node_->zone) Node(node_->zone, node_); } 283594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org void pop() { node_ = node_->previous; } 284594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org bool is_empty() { return node_ == NULL; } 285594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 286594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org bool Contains(Var var) { 287594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org ASSERT(var != kNoVar); 288594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org for (Node* node = node_; node != NULL; node = node->previous) { 289594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (node->effects.Contains(var)) return true; 290594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 291594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return false; 292594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 293594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 294594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org bool Find(Var var, Locator* locator) { 295594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org ASSERT(var != kNoVar); 296594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org for (Node* node = node_; node != NULL; node = node->previous) { 297594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (node->effects.Find(var, locator)) return true; 298594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 299594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return false; 300594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 301594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 302594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org bool Insert(Var var, Locator* locator); 303594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 304594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org private: 305594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org struct Node: ZoneObject { 306594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Zone* zone; 307594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Effects<Var, kNoVar> effects; 308594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Node* previous; 309594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org explicit Node(Zone* zone, Node* previous = NULL) 310594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org : zone(zone), effects(zone), previous(previous) {} 311594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org }; 312594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 313594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org explicit NestedEffectsBase(Node* node) : node_(node) {} 314594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 315594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Node* node_; 316594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org}; 317594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 318594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 319594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgtemplate<class Var, Var kNoVar> 320594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgbool NestedEffectsBase<Var, kNoVar>::Insert(Var var, Locator* locator) { 321594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org ASSERT(var != kNoVar); 322594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (!node_->effects.Insert(var, locator)) return false; 323594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org Locator shadowed; 324594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org for (Node* node = node_->previous; node != NULL; node = node->previous) { 325594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org if (node->effects.Find(var, &shadowed)) { 326594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Initialize with shadowed entry. 327594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org locator->set_value(shadowed.value()); 328594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return false; 329594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 330594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 331594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return true; 332594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org} 333594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 334594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 335594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgtemplate<class Var, Var kNoVar> 336594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.orgclass NestedEffects: public 337594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> > { 338594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org public: 339594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org explicit NestedEffects(Zone* zone) : 340594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >( 341594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org zone) {} 342594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 343594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // Create an extension of the current effect set. The current set should not 344594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org // be modified while the extension is in use. 345594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org NestedEffects Push() { 346594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org NestedEffects result = *this; 347594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org result.push(); 348594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return result; 349594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 350594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 351594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org NestedEffects Pop() { 352594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org NestedEffects result = *this; 353594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org result.pop(); 354594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org ASSERT(!this->is_empty()); 355594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org return result; 356594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org } 357594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org}; 358594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 359594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org} } // namespace v8::internal 360594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org 361594006017e46d82ed7146611dc12c20e3c509c7ddanno@chromium.org#endif // V8_EFFECTS_H_ 362