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 "DFGStrengthReductionPhase.h" 28 29#if ENABLE(DFG_JIT) 30 31#include "DFGGraph.h" 32#include "DFGInsertionSet.h" 33#include "DFGPhase.h" 34#include "DFGPredictionPropagationPhase.h" 35#include "DFGVariableAccessDataDump.h" 36#include "JSCInlines.h" 37 38namespace JSC { namespace DFG { 39 40class StrengthReductionPhase : public Phase { 41public: 42 StrengthReductionPhase(Graph& graph) 43 : Phase(graph, "strength reduction") 44 , m_insertionSet(graph) 45 { 46 } 47 48 bool run() 49 { 50 ASSERT(m_graph.m_fixpointState == FixpointNotConverged); 51 52 m_changed = false; 53 54 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) { 55 m_block = m_graph.block(blockIndex); 56 if (!m_block) 57 continue; 58 for (m_nodeIndex = 0; m_nodeIndex < m_block->size(); ++m_nodeIndex) { 59 m_node = m_block->at(m_nodeIndex); 60 handleNode(); 61 } 62 m_insertionSet.execute(m_block); 63 } 64 65 return m_changed; 66 } 67 68private: 69 void handleNode() 70 { 71 switch (m_node->op()) { 72 case BitOr: 73 handleCommutativity(); 74 75 if (m_node->child2()->isConstant()) { 76 JSValue op2 = m_graph.valueOfJSConstant(m_node->child2().node()); 77 if (op2.isInt32() && !op2.asInt32()) { 78 convertToIdentityOverChild1(); 79 break; 80 } 81 } 82 break; 83 84 case BitXor: 85 case BitAnd: 86 handleCommutativity(); 87 break; 88 89 case BitLShift: 90 case BitRShift: 91 case BitURShift: 92 if (m_node->child2()->isConstant()) { 93 JSValue op2 = m_graph.valueOfJSConstant(m_node->child2().node()); 94 if (op2.isInt32() && !(op2.asInt32() & 0x1f)) { 95 convertToIdentityOverChild1(); 96 break; 97 } 98 } 99 break; 100 101 case UInt32ToNumber: 102 if (m_node->child1()->op() == BitURShift 103 && m_node->child1()->child2()->isConstant()) { 104 JSValue shiftAmount = m_graph.valueOfJSConstant( 105 m_node->child1()->child2().node()); 106 if (shiftAmount.isInt32() && (shiftAmount.asInt32() & 0x1f) 107 && m_node->arithMode() != Arith::DoOverflow) { 108 m_node->convertToIdentity(); 109 m_changed = true; 110 break; 111 } 112 } 113 break; 114 115 case ArithAdd: 116 handleCommutativity(); 117 118 if (m_graph.isInt32Constant(m_node->child2().node())) { 119 int32_t value = m_graph.valueOfInt32Constant( 120 m_node->child2().node()); 121 if (!value) { 122 convertToIdentityOverChild1(); 123 break; 124 } 125 } 126 break; 127 128 case ArithMul: 129 handleCommutativity(); 130 break; 131 132 case ArithSub: 133 if (m_graph.isInt32Constant(m_node->child2().node()) 134 && m_node->isBinaryUseKind(Int32Use)) { 135 int32_t value = m_graph.valueOfInt32Constant(m_node->child2().node()); 136 if (-value != value) { 137 m_node->setOp(ArithAdd); 138 m_node->child2().setNode( 139 m_insertionSet.insertConstant( 140 m_nodeIndex, m_node->origin, jsNumber(-value))); 141 m_changed = true; 142 break; 143 } 144 } 145 break; 146 147 case GetArrayLength: 148 if (JSArrayBufferView* view = m_graph.tryGetFoldableViewForChild1(m_node)) 149 foldTypedArrayPropertyToConstant(view, jsNumber(view->length())); 150 break; 151 152 case GetTypedArrayByteOffset: 153 if (JSArrayBufferView* view = m_graph.tryGetFoldableView(m_node->child1().node())) 154 foldTypedArrayPropertyToConstant(view, jsNumber(view->byteOffset())); 155 break; 156 157 case GetIndexedPropertyStorage: 158 if (JSArrayBufferView* view = m_graph.tryGetFoldableViewForChild1(m_node)) { 159 if (view->mode() != FastTypedArray) { 160 prepareToFoldTypedArray(view); 161 m_node->convertToConstantStoragePointer(view->vector()); 162 m_changed = true; 163 break; 164 } else { 165 // FIXME: It would be awesome to be able to fold the property storage for 166 // these GC-allocated typed arrays. For now it doesn't matter because the 167 // most common use-cases for constant typed arrays involve large arrays with 168 // aliased buffer views. 169 // https://bugs.webkit.org/show_bug.cgi?id=125425 170 } 171 } 172 break; 173 174 case ValueRep: 175 case Int52Rep: 176 case DoubleRep: { 177 // This short-circuits circuitous conversions, like ValueRep(DoubleRep(value)) or 178 // even more complicated things. Like, it can handle a beast like 179 // ValueRep(DoubleRep(Int52Rep(value))). 180 181 // The only speculation that we would do beyond validating that we have a type that 182 // can be represented a certain way is an Int32 check that would appear on Int52Rep 183 // nodes. For now, if we see this and the final type we want is an Int52, we use it 184 // as an excuse not to fold. The only thing we would need is a Int52RepInt32Use kind. 185 bool hadInt32Check = false; 186 if (m_node->op() == Int52Rep) { 187 if (m_node->child1().useKind() != Int32Use) 188 break; 189 hadInt32Check = true; 190 } 191 for (Node* node = m_node->child1().node(); ; node = node->child1().node()) { 192 if (canonicalResultRepresentation(node->result()) == 193 canonicalResultRepresentation(m_node->result())) { 194 m_insertionSet.insertNode( 195 m_nodeIndex, SpecNone, Phantom, m_node->origin, m_node->child1()); 196 if (hadInt32Check) { 197 // FIXME: Consider adding Int52RepInt32Use or even DoubleRepInt32Use, 198 // which would be super weird. The latter would only arise in some 199 // seriously circuitous conversions. 200 if (canonicalResultRepresentation(node->result()) != NodeResultJS) 201 break; 202 203 m_insertionSet.insertNode( 204 m_nodeIndex, SpecNone, Phantom, m_node->origin, 205 Edge(node, Int32Use)); 206 } 207 m_node->child1() = node->defaultEdge(); 208 m_node->convertToIdentity(); 209 m_changed = true; 210 break; 211 } 212 213 switch (node->op()) { 214 case Int52Rep: 215 if (node->child1().useKind() != Int32Use) 216 break; 217 hadInt32Check = true; 218 continue; 219 220 case DoubleRep: 221 case ValueRep: 222 continue; 223 224 default: 225 break; 226 } 227 break; 228 } 229 break; 230 } 231 232 default: 233 break; 234 } 235 } 236 237 void convertToIdentityOverChild(unsigned childIndex) 238 { 239 m_insertionSet.insertNode( 240 m_nodeIndex, SpecNone, Phantom, m_node->origin, m_node->children); 241 m_node->children.removeEdge(childIndex ^ 1); 242 m_node->convertToIdentity(); 243 m_changed = true; 244 } 245 246 void convertToIdentityOverChild1() 247 { 248 convertToIdentityOverChild(0); 249 } 250 251 void convertToIdentityOverChild2() 252 { 253 convertToIdentityOverChild(1); 254 } 255 256 void foldTypedArrayPropertyToConstant(JSArrayBufferView* view, JSValue constant) 257 { 258 prepareToFoldTypedArray(view); 259 m_graph.convertToConstant(m_node, constant); 260 m_changed = true; 261 } 262 263 void prepareToFoldTypedArray(JSArrayBufferView* view) 264 { 265 m_insertionSet.insertNode( 266 m_nodeIndex, SpecNone, TypedArrayWatchpoint, m_node->origin, 267 OpInfo(view)); 268 m_insertionSet.insertNode( 269 m_nodeIndex, SpecNone, Phantom, m_node->origin, m_node->children); 270 } 271 272 void handleCommutativity() 273 { 274 // If the right side is a constant then there is nothing left to do. 275 if (m_node->child2()->hasConstant()) 276 return; 277 278 // This case ensures that optimizations that look for x + const don't also have 279 // to look for const + x. 280 if (m_node->child1()->hasConstant()) { 281 std::swap(m_node->child1(), m_node->child2()); 282 m_changed = true; 283 return; 284 } 285 286 // This case ensures that CSE is commutativity-aware. 287 if (m_node->child1().node() > m_node->child2().node()) { 288 std::swap(m_node->child1(), m_node->child2()); 289 m_changed = true; 290 return; 291 } 292 } 293 294 InsertionSet m_insertionSet; 295 BasicBlock* m_block; 296 unsigned m_nodeIndex; 297 Node* m_node; 298 bool m_changed; 299}; 300 301bool performStrengthReduction(Graph& graph) 302{ 303 SamplingRegion samplingRegion("DFG Strength Reduction Phase"); 304 return runPhase<StrengthReductionPhase>(graph); 305} 306 307} } // namespace JSC::DFG 308 309#endif // ENABLE(DFG_JIT) 310 311