1/* 2 * Copyright (C) 2013 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 "Operations.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 for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) { 48 BasicBlock* block = m_graph.m_blocks[blockIndex].get(); 49 if (!block) 50 continue; 51 52 // Prevent a tower of overflowing additions from creating a value that is out of the 53 // safe 2^48 range. 54 m_allowNestedOverflowingAdditions = block->size() < (1 << 16); 55 56 for (unsigned indexInBlock = block->size(); indexInBlock--;) 57 propagate(block->at(indexInBlock)); 58 } 59 60 return true; 61 } 62 63private: 64 bool isNotNegZero(Node* node) 65 { 66 if (!m_graph.isNumberConstant(node)) 67 return false; 68 double value = m_graph.valueOfNumberConstant(node); 69 return (value || 1.0 / value > 0.0); 70 } 71 72 bool isNotPosZero(Node* node) 73 { 74 if (!m_graph.isNumberConstant(node)) 75 return false; 76 double value = m_graph.valueOfNumberConstant(node); 77 return (value || 1.0 / value < 0.0); 78 } 79 80 // Tests if the absolute value is strictly less than the power of two. 81 template<int power> 82 bool isWithinPowerOfTwoForConstant(Node* node) 83 { 84 JSValue immediateValue = node->valueOfJSConstant(codeBlock()); 85 if (!immediateValue.isNumber()) 86 return false; 87 double immediate = immediateValue.asNumber(); 88 return immediate > -(static_cast<int64_t>(1) << power) && immediate < (static_cast<int64_t>(1) << power); 89 } 90 91 template<int power> 92 bool isWithinPowerOfTwoNonRecursive(Node* node) 93 { 94 if (node->op() != JSConstant) 95 return false; 96 return isWithinPowerOfTwoForConstant<power>(node); 97 } 98 99 template<int power> 100 bool isWithinPowerOfTwo(Node* node) 101 { 102 switch (node->op()) { 103 case JSConstant: { 104 return isWithinPowerOfTwoForConstant<power>(node); 105 } 106 107 case BitAnd: { 108 if (power > 31) 109 return true; 110 111 return isWithinPowerOfTwoNonRecursive<power>(node->child1().node()) 112 || isWithinPowerOfTwoNonRecursive<power>(node->child2().node()); 113 } 114 115 case BitOr: 116 case BitXor: 117 case BitLShift: 118 case ValueToInt32: { 119 return power > 31; 120 } 121 122 case BitRShift: 123 case BitURShift: { 124 if (power > 31) 125 return true; 126 127 Node* shiftAmount = node->child2().node(); 128 if (shiftAmount->op() != JSConstant) 129 return false; 130 JSValue immediateValue = shiftAmount->valueOfJSConstant(codeBlock()); 131 if (!immediateValue.isInt32()) 132 return false; 133 return immediateValue.asInt32() > 32 - power; 134 } 135 136 default: 137 return false; 138 } 139 } 140 141 template<int power> 142 bool isWithinPowerOfTwo(Edge edge) 143 { 144 return isWithinPowerOfTwo<power>(edge.node()); 145 } 146 147 bool mergeDefaultFlags(Node* node) 148 { 149 bool changed = false; 150 if (node->flags() & NodeHasVarArgs) { 151 for (unsigned childIdx = node->firstChild(); 152 childIdx < node->firstChild() + node->numChildren(); 153 childIdx++) { 154 if (!!m_graph.m_varArgChildren[childIdx]) 155 changed |= m_graph.m_varArgChildren[childIdx]->mergeFlags(NodeUsedAsValue); 156 } 157 } else { 158 if (!node->child1()) 159 return changed; 160 changed |= node->child1()->mergeFlags(NodeUsedAsValue); 161 if (!node->child2()) 162 return changed; 163 changed |= node->child2()->mergeFlags(NodeUsedAsValue); 164 if (!node->child3()) 165 return changed; 166 changed |= node->child3()->mergeFlags(NodeUsedAsValue); 167 } 168 return changed; 169 } 170 171 void propagate(Node* node) 172 { 173 NodeFlags flags = node->flags() & NodeBackPropMask; 174 175 switch (node->op()) { 176 case GetLocal: { 177 VariableAccessData* variableAccessData = node->variableAccessData(); 178 variableAccessData->mergeFlags(flags); 179 break; 180 } 181 182 case SetLocal: { 183 VariableAccessData* variableAccessData = node->variableAccessData(); 184 if (!variableAccessData->isLoadedFrom()) 185 break; 186 node->child1()->mergeFlags(NodeUsedAsValue); 187 break; 188 } 189 190 case BitAnd: 191 case BitOr: 192 case BitXor: 193 case BitRShift: 194 case BitLShift: 195 case BitURShift: 196 case ArithIMul: { 197 flags |= NodeUsedAsInt; 198 flags &= ~(NodeUsedAsNumber | NodeNeedsNegZero | NodeUsedAsOther); 199 node->child1()->mergeFlags(flags); 200 node->child2()->mergeFlags(flags); 201 break; 202 } 203 204 case ValueToInt32: { 205 flags |= NodeUsedAsInt; 206 flags &= ~(NodeUsedAsNumber | NodeNeedsNegZero | NodeUsedAsOther); 207 node->child1()->mergeFlags(flags); 208 break; 209 } 210 211 case StringCharCodeAt: { 212 node->child1()->mergeFlags(NodeUsedAsValue); 213 node->child2()->mergeFlags(NodeUsedAsValue | NodeUsedAsInt); 214 break; 215 } 216 217 case Identity: 218 case UInt32ToNumber: { 219 node->child1()->mergeFlags(flags); 220 break; 221 } 222 223 case ValueAdd: { 224 if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node())) 225 flags &= ~NodeNeedsNegZero; 226 if (node->child1()->hasNumberResult() || node->child2()->hasNumberResult()) 227 flags &= ~NodeUsedAsOther; 228 if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2())) 229 flags |= NodeUsedAsNumber; 230 if (!m_allowNestedOverflowingAdditions) 231 flags |= NodeUsedAsNumber; 232 233 node->child1()->mergeFlags(flags); 234 node->child2()->mergeFlags(flags); 235 break; 236 } 237 238 case ArithAdd: { 239 if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node())) 240 flags &= ~NodeNeedsNegZero; 241 if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2())) 242 flags |= NodeUsedAsNumber; 243 if (!m_allowNestedOverflowingAdditions) 244 flags |= NodeUsedAsNumber; 245 246 node->child1()->mergeFlags(flags); 247 node->child2()->mergeFlags(flags); 248 break; 249 } 250 251 case ArithSub: { 252 if (isNotNegZero(node->child1().node()) || isNotPosZero(node->child2().node())) 253 flags &= ~NodeNeedsNegZero; 254 if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2())) 255 flags |= NodeUsedAsNumber; 256 if (!m_allowNestedOverflowingAdditions) 257 flags |= NodeUsedAsNumber; 258 259 node->child1()->mergeFlags(flags); 260 node->child2()->mergeFlags(flags); 261 break; 262 } 263 264 case ArithNegate: { 265 flags &= ~NodeUsedAsOther; 266 267 node->child1()->mergeFlags(flags); 268 break; 269 } 270 271 case ArithMul: { 272 // As soon as a multiply happens, we can easily end up in the part 273 // of the double domain where the point at which you do truncation 274 // can change the outcome. So, ArithMul always forces its inputs to 275 // check for overflow. Additionally, it will have to check for overflow 276 // itself unless we can prove that there is no way for the values 277 // produced to cause double rounding. 278 279 if (!isWithinPowerOfTwo<22>(node->child1().node()) 280 && !isWithinPowerOfTwo<22>(node->child2().node())) 281 flags |= NodeUsedAsNumber; 282 283 node->mergeFlags(flags); 284 285 flags |= NodeUsedAsNumber | NodeNeedsNegZero; 286 flags &= ~NodeUsedAsOther; 287 288 node->child1()->mergeFlags(flags); 289 node->child2()->mergeFlags(flags); 290 break; 291 } 292 293 case ArithDiv: { 294 flags |= NodeUsedAsNumber | NodeNeedsNegZero; 295 flags &= ~NodeUsedAsOther; 296 297 node->child1()->mergeFlags(flags); 298 node->child2()->mergeFlags(flags); 299 break; 300 } 301 302 case ArithMod: { 303 flags |= NodeUsedAsNumber | NodeNeedsNegZero; 304 flags &= ~NodeUsedAsOther; 305 306 node->child1()->mergeFlags(flags); 307 node->child2()->mergeFlags(flags); 308 break; 309 } 310 311 case GetByVal: { 312 node->child1()->mergeFlags(NodeUsedAsValue); 313 node->child2()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt); 314 break; 315 } 316 317 case GetMyArgumentByValSafe: { 318 node->child1()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt); 319 break; 320 } 321 322 case NewArrayWithSize: { 323 node->child1()->mergeFlags(NodeUsedAsValue | NodeUsedAsInt); 324 break; 325 } 326 327 case StringCharAt: { 328 node->child1()->mergeFlags(NodeUsedAsValue); 329 node->child2()->mergeFlags(NodeUsedAsValue | NodeUsedAsInt); 330 break; 331 } 332 333 case ToString: { 334 node->child1()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther); 335 break; 336 } 337 338 case ToPrimitive: { 339 node->child1()->mergeFlags(flags); 340 break; 341 } 342 343 case PutByVal: { 344 m_graph.varArgChild(node, 0)->mergeFlags(NodeUsedAsValue); 345 m_graph.varArgChild(node, 1)->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt); 346 m_graph.varArgChild(node, 2)->mergeFlags(NodeUsedAsValue); 347 break; 348 } 349 350 default: 351 mergeDefaultFlags(node); 352 break; 353 } 354 } 355 356 bool m_allowNestedOverflowingAdditions; 357}; 358 359bool performBackwardsPropagation(Graph& graph) 360{ 361 SamplingRegion samplingRegion("DFG Backwards Propagation Phase"); 362 return runPhase<BackwardsPropagationPhase>(graph); 363} 364 365} } // namespace JSC::DFG 366 367#endif // ENABLE(DFG_JIT) 368 369