1/* 2 * Copyright (C) 2011, 2012, 2013, 2014 Apple Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26#ifndef DFGAbstractValue_h 27#define DFGAbstractValue_h 28 29#if ENABLE(DFG_JIT) 30 31#include "ArrayProfile.h" 32#include "DFGFiltrationResult.h" 33#include "DFGNodeFlags.h" 34#include "DFGStructureAbstractValue.h" 35#include "JSCell.h" 36#include "SpeculatedType.h" 37#include "DumpContext.h" 38#include "StructureSet.h" 39 40namespace JSC { namespace DFG { 41 42class Graph; 43struct Node; 44 45struct AbstractValue { 46 AbstractValue() 47 : m_type(SpecNone) 48 , m_arrayModes(0) 49 { 50 } 51 52 void clear() 53 { 54 m_type = SpecNone; 55 m_arrayModes = 0; 56 m_currentKnownStructure.clear(); 57 m_futurePossibleStructure.clear(); 58 m_value = JSValue(); 59 checkConsistency(); 60 } 61 62 bool isClear() const { return m_type == SpecNone; } 63 bool operator!() const { return isClear(); } 64 65 void makeHeapTop() 66 { 67 makeTop(SpecHeapTop); 68 } 69 70 void makeBytecodeTop() 71 { 72 makeTop(SpecBytecodeTop); 73 } 74 75 void clobberStructures() 76 { 77 if (m_type & SpecCell) { 78 m_currentKnownStructure.makeTop(); 79 clobberArrayModes(); 80 } else { 81 ASSERT(m_currentKnownStructure.isClear()); 82 ASSERT(!m_arrayModes); 83 } 84 checkConsistency(); 85 } 86 87 void clobberValue() 88 { 89 m_value = JSValue(); 90 } 91 92 bool isHeapTop() const 93 { 94 return (m_type | SpecHeapTop) == m_type && m_currentKnownStructure.isTop() && m_futurePossibleStructure.isTop(); 95 } 96 97 bool valueIsTop() const 98 { 99 return !m_value && m_type; 100 } 101 102 JSValue value() const 103 { 104 return m_value; 105 } 106 107 static AbstractValue heapTop() 108 { 109 AbstractValue result; 110 result.makeHeapTop(); 111 return result; 112 } 113 114 void setMostSpecific(Graph&, JSValue); 115 void set(Graph&, JSValue); 116 void set(Graph&, Structure*); 117 118 void setType(SpeculatedType type) 119 { 120 if (type & SpecCell) { 121 m_currentKnownStructure.makeTop(); 122 m_futurePossibleStructure.makeTop(); 123 m_arrayModes = ALL_ARRAY_MODES; 124 } else { 125 m_currentKnownStructure.clear(); 126 m_futurePossibleStructure.clear(); 127 m_arrayModes = 0; 128 } 129 m_type = type; 130 m_value = JSValue(); 131 checkConsistency(); 132 } 133 134 void fixTypeForRepresentation(NodeFlags representation); 135 void fixTypeForRepresentation(Node*); 136 137 bool operator==(const AbstractValue& other) const 138 { 139 return m_type == other.m_type 140 && m_arrayModes == other.m_arrayModes 141 && m_currentKnownStructure == other.m_currentKnownStructure 142 && m_futurePossibleStructure == other.m_futurePossibleStructure 143 && m_value == other.m_value; 144 } 145 bool operator!=(const AbstractValue& other) const 146 { 147 return !(*this == other); 148 } 149 150 bool merge(const AbstractValue& other) 151 { 152 if (other.isClear()) 153 return false; 154 155#if !ASSERT_DISABLED 156 AbstractValue oldMe = *this; 157#endif 158 bool result = false; 159 if (isClear()) { 160 *this = other; 161 result = !other.isClear(); 162 } else { 163 result |= mergeSpeculation(m_type, other.m_type); 164 result |= mergeArrayModes(m_arrayModes, other.m_arrayModes); 165 result |= m_currentKnownStructure.addAll(other.m_currentKnownStructure); 166 result |= m_futurePossibleStructure.addAll(other.m_futurePossibleStructure); 167 if (m_value != other.m_value) { 168 result |= !!m_value; 169 m_value = JSValue(); 170 } 171 } 172 checkConsistency(); 173 ASSERT(result == (*this != oldMe)); 174 return result; 175 } 176 177 void merge(SpeculatedType type) 178 { 179 mergeSpeculation(m_type, type); 180 181 if (type & SpecCell) { 182 m_currentKnownStructure.makeTop(); 183 m_futurePossibleStructure.makeTop(); 184 m_arrayModes = ALL_ARRAY_MODES; 185 } 186 m_value = JSValue(); 187 188 checkConsistency(); 189 } 190 191 bool couldBeType(SpeculatedType desiredType) 192 { 193 return !!(m_type & desiredType); 194 } 195 196 bool isType(SpeculatedType desiredType) 197 { 198 return !(m_type & ~desiredType); 199 } 200 201 FiltrationResult filter(Graph&, const StructureSet&); 202 203 FiltrationResult filterArrayModes(ArrayModes); 204 205 FiltrationResult filter(SpeculatedType); 206 207 FiltrationResult filterByValue(JSValue); 208 209 bool validate(JSValue value) const 210 { 211 if (isHeapTop()) 212 return true; 213 214 if (!!m_value && m_value != value) 215 return false; 216 217 if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type) 218 return false; 219 220 if (value.isEmpty()) { 221 ASSERT(m_type & SpecEmpty); 222 return true; 223 } 224 225 if (!!value && value.isCell()) { 226 ASSERT(m_type & SpecCell); 227 Structure* structure = value.asCell()->structure(); 228 return m_currentKnownStructure.contains(structure) 229 && m_futurePossibleStructure.contains(structure) 230 && (m_arrayModes & asArrayModes(structure->indexingType())); 231 } 232 233 return true; 234 } 235 236 Structure* bestProvenStructure() const 237 { 238 if (m_currentKnownStructure.hasSingleton()) 239 return m_currentKnownStructure.singleton(); 240 if (m_futurePossibleStructure.hasSingleton()) 241 return m_futurePossibleStructure.singleton(); 242 return 0; 243 } 244 245 bool hasClobberableState() const 246 { 247 return m_currentKnownStructure.isNeitherClearNorTop() 248 || !arrayModesAreClearOrTop(m_arrayModes); 249 } 250 251#if ASSERT_DISABLED 252 void checkConsistency() const { } 253#else 254 void checkConsistency() const; 255#endif 256 257 void dumpInContext(PrintStream&, DumpContext*) const; 258 void dump(PrintStream&) const; 259 260 // A great way to think about the difference between m_currentKnownStructure and 261 // m_futurePossibleStructure is to consider these four examples: 262 // 263 // 1) x = foo(); 264 // 265 // In this case x's m_currentKnownStructure and m_futurePossibleStructure will 266 // both be TOP, since we don't know anything about x for sure, yet. 267 // 268 // 2) x = foo(); 269 // y = x.f; 270 // 271 // Where x will later have a new property added to it, 'g'. Because of the 272 // known but not-yet-executed property addition, x's current structure will 273 // not be watchpointable; hence we have no way of statically bounding the set 274 // of possible structures that x may have if a clobbering event happens. So, 275 // x's m_currentKnownStructure will be whatever structure we check to get 276 // property 'f', and m_futurePossibleStructure will be TOP. 277 // 278 // 3) x = foo(); 279 // y = x.f; 280 // 281 // Where x has a terminal structure that is still watchpointable. In this case, 282 // x's m_currentKnownStructure and m_futurePossibleStructure will both be 283 // whatever structure we checked for when getting 'f'. 284 // 285 // 4) x = foo(); 286 // y = x.f; 287 // bar(); 288 // 289 // Where x has a terminal structure that is still watchpointable. In this 290 // case, m_currentKnownStructure will be TOP because bar() may potentially 291 // change x's structure and we have no way of proving otherwise, but 292 // x's m_futurePossibleStructure will be whatever structure we had checked 293 // when getting property 'f'. 294 295 // NB. All fields in this struct must have trivial destructors. 296 297 // This is a proven constraint on the structures that this value can have right 298 // now. The structure of the current value must belong to this set. The set may 299 // be TOP, indicating that it is the set of all possible structures, in which 300 // case the current value can have any structure. The set may be BOTTOM (empty) 301 // in which case this value cannot be a cell. This is all subject to change 302 // anytime a new value is assigned to this one, anytime there is a control flow 303 // merge, or most crucially, anytime a side-effect or structure check happens. 304 // In case of a side-effect, we typically must assume that any value may have 305 // had its structure changed, hence contravening our proof. We make the proof 306 // valid again by switching this to TOP (i.e. claiming that we have proved that 307 // this value may have any structure). Of note is that the proof represented by 308 // this field is not subject to structure transition watchpoints - even if one 309 // fires, we can be sure that this proof is still valid. 310 StructureAbstractValue m_currentKnownStructure; 311 312 // This is a proven constraint on the structures that this value can have now 313 // or any time in the future subject to the structure transition watchpoints of 314 // all members of this set not having fired. This set is impervious to side- 315 // effects; even if one happens the side-effect can only cause the value to 316 // change to at worst another structure that is also a member of this set. But, 317 // the theorem being proved by this field is predicated upon there not being 318 // any new structure transitions introduced into any members of this set. In 319 // cases where there is no way for us to guard this happening, the set must be 320 // TOP. But in cases where we can guard new structure transitions (all members 321 // of the set have still-valid structure transition watchpoints) then this set 322 // will be finite. Anytime that we make use of the finite nature of this set, 323 // we must first issue a structure transition watchpoint, which will effectively 324 // result in m_currentKnownStructure being filtered according to 325 // m_futurePossibleStructure. 326 StructureAbstractValue m_futurePossibleStructure; 327 328 // This is a proven constraint on the possible types that this value can have 329 // now or any time in the future, unless it is reassigned. This field is 330 // impervious to side-effects unless the side-effect can reassign the value 331 // (for example if we're talking about a captured variable). The relationship 332 // between this field, and the structure fields above, is as follows. The 333 // fields above constraint the structures that a cell may have, but they say 334 // nothing about whether or not the value is known to be a cell. More formally, 335 // the m_currentKnownStructure is itself an abstract value that consists of the 336 // union of the set of all non-cell values and the set of cell values that have 337 // the given structure. This abstract value is then the intersection of the 338 // m_currentKnownStructure and the set of values whose type is m_type. So, for 339 // example if m_type is SpecFinal|SpecInt32 and m_currentKnownStructure is 340 // [0x12345] then this abstract value corresponds to the set of all integers 341 // unified with the set of all objects with structure 0x12345. 342 SpeculatedType m_type; 343 344 // This is a proven constraint on the possible indexing types that this value 345 // can have right now. It also implicitly constraints the set of structures 346 // that the value may have right now, since a structure has an immutable 347 // indexing type. This is subject to change upon reassignment, or any side 348 // effect that makes non-obvious changes to the heap. 349 ArrayModes m_arrayModes; 350 351 // This is a proven constraint on the possible values that this value can 352 // have now or any time in the future, unless it is reassigned. Note that this 353 // implies nothing about the structure. Oddly, JSValue() (i.e. the empty value) 354 // means either BOTTOM or TOP depending on the state of m_type: if m_type is 355 // BOTTOM then JSValue() means BOTTOM; if m_type is not BOTTOM then JSValue() 356 // means TOP. 357 JSValue m_value; 358 359private: 360 void clobberArrayModes() 361 { 362 // FIXME: We could make this try to predict the set of array modes that this object 363 // could have in the future. For now, just do the simple thing. 364 m_arrayModes = ALL_ARRAY_MODES; 365 } 366 367 bool validateType(JSValue value) const 368 { 369 if (isHeapTop()) 370 return true; 371 372 // Constant folding always represents Int52's in a double (i.e. Int52AsDouble). 373 // So speculationFromValue(value) for an Int52 value will return Int52AsDouble, 374 // and that's fine - the type validates just fine. 375 SpeculatedType type = m_type; 376 if (type & SpecInt52) 377 type |= SpecInt52AsDouble; 378 379 if (mergeSpeculations(type, speculationFromValue(value)) != type) 380 return false; 381 382 if (value.isEmpty()) { 383 ASSERT(m_type & SpecEmpty); 384 return true; 385 } 386 387 return true; 388 } 389 390 void makeTop(SpeculatedType top) 391 { 392 m_type |= top; 393 m_arrayModes = ALL_ARRAY_MODES; 394 m_currentKnownStructure.makeTop(); 395 m_futurePossibleStructure.makeTop(); 396 m_value = JSValue(); 397 checkConsistency(); 398 } 399 400 void setFuturePossibleStructure(Graph&, Structure*); 401 402 void filterValueByType(); 403 void filterArrayModesByType(); 404 405 bool shouldBeClear() const; 406 FiltrationResult normalizeClarity(); 407}; 408 409} } // namespace JSC::DFG 410 411#endif // ENABLE(DFG_JIT) 412 413#endif // DFGAbstractValue_h 414 415 416