1/* 2 * Copyright (C) 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#include "config.h" 27#include "DFGBackwardsPropagationPhase.h" 28 29#if ENABLE(DFG_JIT) 30 31#include "DFGBasicBlockInlines.h" 32#include "DFGGraph.h" 33#include "DFGPhase.h" 34#include "JSCInlines.h" 35 36namespace JSC { namespace DFG { 37 38class BackwardsPropagationPhase : public Phase { 39public: 40 BackwardsPropagationPhase(Graph& graph) 41 : Phase(graph, "backwards propagation") 42 { 43 } 44 45 bool run() 46 { 47 m_changed = true; 48 while (m_changed) { 49 m_changed = false; 50 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) { 51 BasicBlock* block = m_graph.block(blockIndex); 52 if (!block) 53 continue; 54 55 // Prevent a tower of overflowing additions from creating a value that is out of the 56 // safe 2^48 range. 57 m_allowNestedOverflowingAdditions = block->size() < (1 << 16); 58 59 for (unsigned indexInBlock = block->size(); indexInBlock--;) 60 propagate(block->at(indexInBlock)); 61 } 62 } 63 64 return true; 65 } 66 67private: 68 bool isNotNegZero(Node* node) 69 { 70 if (!m_graph.isNumberConstant(node)) 71 return false; 72 double value = m_graph.valueOfNumberConstant(node); 73 return (value || 1.0 / value > 0.0); 74 } 75 76 bool isNotPosZero(Node* node) 77 { 78 if (!m_graph.isNumberConstant(node)) 79 return false; 80 double value = m_graph.valueOfNumberConstant(node); 81 return (value || 1.0 / value < 0.0); 82 } 83 84 // Tests if the absolute value is strictly less than the power of two. 85 template<int power> 86 bool isWithinPowerOfTwoForConstant(Node* node) 87 { 88 JSValue immediateValue = node->valueOfJSConstant(codeBlock()); 89 if (!immediateValue.isNumber()) 90 return false; 91 double immediate = immediateValue.asNumber(); 92 return immediate > -(static_cast<int64_t>(1) << power) && immediate < (static_cast<int64_t>(1) << power); 93 } 94 95 template<int power> 96 bool isWithinPowerOfTwoNonRecursive(Node* node) 97 { 98 if (node->op() != JSConstant) 99 return false; 100 return isWithinPowerOfTwoForConstant<power>(node); 101 } 102 103 template<int power> 104 bool isWithinPowerOfTwo(Node* node) 105 { 106 switch (node->op()) { 107 case JSConstant: { 108 return isWithinPowerOfTwoForConstant<power>(node); 109 } 110 111 case BitAnd: { 112 if (power > 31) 113 return true; 114 115 return isWithinPowerOfTwoNonRecursive<power>(node->child1().node()) 116 || isWithinPowerOfTwoNonRecursive<power>(node->child2().node()); 117 } 118 119 case BitOr: 120 case BitXor: 121 case BitLShift: { 122 return power > 31; 123 } 124 125 case BitRShift: 126 case BitURShift: { 127 if (power > 31) 128 return true; 129 130 Node* shiftAmount = node->child2().node(); 131 if (shiftAmount->op() != JSConstant) 132 return false; 133 JSValue immediateValue = shiftAmount->valueOfJSConstant(codeBlock()); 134 if (!immediateValue.isInt32()) 135 return false; 136 return immediateValue.asInt32() > 32 - power; 137 } 138 139 default: 140 return false; 141 } 142 } 143 144 template<int power> 145 bool isWithinPowerOfTwo(Edge edge) 146 { 147 return isWithinPowerOfTwo<power>(edge.node()); 148 } 149 150 bool mergeDefaultFlags(Node* node) 151 { 152 bool changed = false; 153 if (node->flags() & NodeHasVarArgs) { 154 for (unsigned childIdx = node->firstChild(); 155 childIdx < node->firstChild() + node->numChildren(); 156 childIdx++) { 157 if (!!m_graph.m_varArgChildren[childIdx]) 158 changed |= m_graph.m_varArgChildren[childIdx]->mergeFlags(NodeBytecodeUsesAsValue); 159 } 160 } else { 161 if (!node->child1()) 162 return changed; 163 changed |= node->child1()->mergeFlags(NodeBytecodeUsesAsValue); 164 if (!node->child2()) 165 return changed; 166 changed |= node->child2()->mergeFlags(NodeBytecodeUsesAsValue); 167 if (!node->child3()) 168 return changed; 169 changed |= node->child3()->mergeFlags(NodeBytecodeUsesAsValue); 170 } 171 return changed; 172 } 173 174 void propagate(Node* node) 175 { 176 NodeFlags flags = node->flags() & NodeBytecodeBackPropMask; 177 178 switch (node->op()) { 179 case GetLocal: { 180 VariableAccessData* variableAccessData = node->variableAccessData(); 181 flags &= ~NodeBytecodeUsesAsInt; // We don't care about cross-block uses-as-int. 182 m_changed |= variableAccessData->mergeFlags(flags); 183 break; 184 } 185 186 case SetLocal: { 187 VariableAccessData* variableAccessData = node->variableAccessData(); 188 if (!variableAccessData->isLoadedFrom()) 189 break; 190 flags = variableAccessData->flags(); 191 RELEASE_ASSERT(!(flags & ~NodeBytecodeBackPropMask)); 192 flags |= NodeBytecodeUsesAsNumber; // Account for the fact that control flow may cause overflows that our modeling can't handle. 193 node->child1()->mergeFlags(flags); 194 break; 195 } 196 197 case Flush: { 198 VariableAccessData* variableAccessData = node->variableAccessData(); 199 m_changed |= variableAccessData->mergeFlags(NodeBytecodeUsesAsValue); 200 break; 201 } 202 203 case MovHint: 204 case Check: 205 break; 206 207 case BitAnd: 208 case BitOr: 209 case BitXor: 210 case BitRShift: 211 case BitLShift: 212 case BitURShift: 213 case ArithIMul: { 214 flags |= NodeBytecodeUsesAsInt; 215 flags &= ~(NodeBytecodeUsesAsNumber | NodeBytecodeNeedsNegZero | NodeBytecodeUsesAsOther); 216 flags &= ~NodeBytecodeUsesAsArrayIndex; 217 node->child1()->mergeFlags(flags); 218 node->child2()->mergeFlags(flags); 219 break; 220 } 221 222 case StringCharCodeAt: { 223 node->child1()->mergeFlags(NodeBytecodeUsesAsValue); 224 node->child2()->mergeFlags(NodeBytecodeUsesAsValue | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex); 225 break; 226 } 227 228 case UInt32ToNumber: { 229 node->child1()->mergeFlags(flags); 230 break; 231 } 232 233 case ValueAdd: { 234 if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node())) 235 flags &= ~NodeBytecodeNeedsNegZero; 236 if (node->child1()->hasNumberResult() || node->child2()->hasNumberResult()) 237 flags &= ~NodeBytecodeUsesAsOther; 238 if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2())) 239 flags |= NodeBytecodeUsesAsNumber; 240 if (!m_allowNestedOverflowingAdditions) 241 flags |= NodeBytecodeUsesAsNumber; 242 243 node->child1()->mergeFlags(flags); 244 node->child2()->mergeFlags(flags); 245 break; 246 } 247 248 case ArithAdd: { 249 if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node())) 250 flags &= ~NodeBytecodeNeedsNegZero; 251 if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2())) 252 flags |= NodeBytecodeUsesAsNumber; 253 if (!m_allowNestedOverflowingAdditions) 254 flags |= NodeBytecodeUsesAsNumber; 255 256 node->child1()->mergeFlags(flags); 257 node->child2()->mergeFlags(flags); 258 break; 259 } 260 261 case ArithSub: { 262 if (isNotNegZero(node->child1().node()) || isNotPosZero(node->child2().node())) 263 flags &= ~NodeBytecodeNeedsNegZero; 264 if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2())) 265 flags |= NodeBytecodeUsesAsNumber; 266 if (!m_allowNestedOverflowingAdditions) 267 flags |= NodeBytecodeUsesAsNumber; 268 269 node->child1()->mergeFlags(flags); 270 node->child2()->mergeFlags(flags); 271 break; 272 } 273 274 case ArithNegate: { 275 flags &= ~NodeBytecodeUsesAsOther; 276 277 node->child1()->mergeFlags(flags); 278 break; 279 } 280 281 case ArithMul: { 282 // As soon as a multiply happens, we can easily end up in the part 283 // of the double domain where the point at which you do truncation 284 // can change the outcome. So, ArithMul always forces its inputs to 285 // check for overflow. Additionally, it will have to check for overflow 286 // itself unless we can prove that there is no way for the values 287 // produced to cause double rounding. 288 289 if (!isWithinPowerOfTwo<22>(node->child1().node()) 290 && !isWithinPowerOfTwo<22>(node->child2().node())) 291 flags |= NodeBytecodeUsesAsNumber; 292 293 node->mergeFlags(flags); 294 295 flags |= NodeBytecodeUsesAsNumber | NodeBytecodeNeedsNegZero; 296 flags &= ~NodeBytecodeUsesAsOther; 297 298 node->child1()->mergeFlags(flags); 299 node->child2()->mergeFlags(flags); 300 break; 301 } 302 303 case ArithDiv: { 304 flags |= NodeBytecodeUsesAsNumber | NodeBytecodeNeedsNegZero; 305 flags &= ~NodeBytecodeUsesAsOther; 306 307 node->child1()->mergeFlags(flags); 308 node->child2()->mergeFlags(flags); 309 break; 310 } 311 312 case ArithMod: { 313 flags |= NodeBytecodeUsesAsNumber | NodeBytecodeNeedsNegZero; 314 flags &= ~NodeBytecodeUsesAsOther; 315 316 node->child1()->mergeFlags(flags); 317 node->child2()->mergeFlags(flags); 318 break; 319 } 320 321 case GetByVal: { 322 node->child1()->mergeFlags(NodeBytecodeUsesAsValue); 323 node->child2()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex); 324 break; 325 } 326 327 case GetMyArgumentByValSafe: { 328 node->child1()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex); 329 break; 330 } 331 332 case NewArrayWithSize: { 333 node->child1()->mergeFlags(NodeBytecodeUsesAsValue | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex); 334 break; 335 } 336 337 case NewTypedArray: { 338 // Negative zero is not observable. NaN versus undefined are only observable 339 // in that you would get a different exception message. So, like, whatever: we 340 // claim here that NaN v. undefined is observable. 341 node->child1()->mergeFlags(NodeBytecodeUsesAsInt | NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther | NodeBytecodeUsesAsArrayIndex); 342 break; 343 } 344 345 case StringCharAt: { 346 node->child1()->mergeFlags(NodeBytecodeUsesAsValue); 347 node->child2()->mergeFlags(NodeBytecodeUsesAsValue | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex); 348 break; 349 } 350 351 case ToString: { 352 node->child1()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther); 353 break; 354 } 355 356 case ToPrimitive: { 357 node->child1()->mergeFlags(flags); 358 break; 359 } 360 361 case PutByValDirect: 362 case PutByVal: { 363 m_graph.varArgChild(node, 0)->mergeFlags(NodeBytecodeUsesAsValue); 364 m_graph.varArgChild(node, 1)->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex); 365 m_graph.varArgChild(node, 2)->mergeFlags(NodeBytecodeUsesAsValue); 366 break; 367 } 368 369 case Switch: { 370 SwitchData* data = node->switchData(); 371 switch (data->kind) { 372 case SwitchImm: 373 // We don't need NodeBytecodeNeedsNegZero because if the cases are all integers 374 // then -0 and 0 are treated the same. We don't need NodeBytecodeUsesAsOther 375 // because if all of the cases are integers then NaN and undefined are 376 // treated the same (i.e. they will take default). 377 node->child1()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsInt); 378 break; 379 case SwitchChar: { 380 // We don't need NodeBytecodeNeedsNegZero because if the cases are all strings 381 // then -0 and 0 are treated the same. We don't need NodeBytecodeUsesAsOther 382 // because if all of the cases are single-character strings then NaN 383 // and undefined are treated the same (i.e. they will take default). 384 node->child1()->mergeFlags(NodeBytecodeUsesAsNumber); 385 break; 386 } 387 case SwitchString: 388 // We don't need NodeBytecodeNeedsNegZero because if the cases are all strings 389 // then -0 and 0 are treated the same. 390 node->child1()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther); 391 break; 392 } 393 break; 394 } 395 396 case Identity: 397 // This would be trivial to handle but we just assert that we cannot see these yet. 398 RELEASE_ASSERT_NOT_REACHED(); 399 break; 400 401 // Note: ArithSqrt, ArithSin, and ArithCos and other math intrinsics don't have special 402 // rules in here because they are always followed by Phantoms to signify that if the 403 // method call speculation fails, the bytecode may use the arguments in arbitrary ways. 404 // This corresponds to that possibility of someone doing something like: 405 // Math.sin = function(x) { doArbitraryThingsTo(x); } 406 407 default: 408 mergeDefaultFlags(node); 409 break; 410 } 411 } 412 413 bool m_allowNestedOverflowingAdditions; 414 bool m_changed; 415}; 416 417bool performBackwardsPropagation(Graph& graph) 418{ 419 SamplingRegion samplingRegion("DFG Backwards Propagation Phase"); 420 return runPhase<BackwardsPropagationPhase>(graph); 421} 422 423} } // namespace JSC::DFG 424 425#endif // ENABLE(DFG_JIT) 426 427