dfg/DFGStrengthReductionPhase.cpp

   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
  38 namespace JSC { namespace DFG {
  39
  40 class StrengthReductionPhase : public Phase {
  41 public:
  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
  68 private:
  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
 301 bool 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