dfg/DFGStrengthReductionPhase.cpp

   1 /*
   2  * Copyright (C) 2013-2015 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 "DFGAbstractHeap.h"
  32 #include "DFGClobberize.h"
  33 #include "DFGGraph.h"
  34 #include "DFGInsertionSet.h"
  35 #include "DFGPhase.h"
  36 #include "DFGPredictionPropagationPhase.h"
  37 #include "DFGVariableAccessDataDump.h"
  38 #include "JSCInlines.h"
  39
  40 namespace JSC { namespace DFG {
  41
  42 class StrengthReductionPhase : public Phase {
  43 public:
  44     StrengthReductionPhase(Graph& graph)
  45         : Phase(graph, "strength reduction")
  46         , m_insertionSet(graph)
  47     {
  48     }
  49
  50     bool run()
  51     {
  52         ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
  53
  54         m_changed = false;
  55
  56         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
  57             m_block = m_graph.block(blockIndex);
  58             if (!m_block)
  59                 continue;
  60             for (m_nodeIndex = 0; m_nodeIndex < m_block->size(); ++m_nodeIndex) {
  61                 m_node = m_block->at(m_nodeIndex);
  62                 handleNode();
  63             }
  64             m_insertionSet.execute(m_block);
  65         }
  66
  67         return m_changed;
  68     }
  69
  70 private:
  71     void handleNode()
  72     {
  73         switch (m_node->op()) {
  74         case BitOr:
  75             handleCommutativity();
  76
  77             if (m_node->child2()->isInt32Constant() && !m_node->child2()->asInt32()) {
  78                 convertToIdentityOverChild1();
  79                 break;
  80             }
  81             break;
  82
  83         case BitXor:
  84         case BitAnd:
  85             handleCommutativity();
  86             break;
  87
  88         case BitLShift:
  89         case BitRShift:
  90         case BitURShift:
  91             if (m_node->child2()->isInt32Constant() && !(m_node->child2()->asInt32() & 0x1f)) {
  92                 convertToIdentityOverChild1();
  93                 break;
  94             }
  95             break;
  96
  97         case UInt32ToNumber:
  98             if (m_node->child1()->op() == BitURShift
  99                 && m_node->child1()->child2()->isInt32Constant()
 100                 && (m_node->child1()->child2()->asInt32() & 0x1f)
 101                 && m_node->arithMode() != Arith::DoOverflow) {
 102                 m_node->convertToIdentity();
 103                 m_changed = true;
 104                 break;
 105             }
 106             break;
 107
 108         case ArithAdd:
 109             handleCommutativity();
 110
 111             if (m_node->child2()->isInt32Constant() && !m_node->child2()->asInt32()) {
 112                 convertToIdentityOverChild1();
 113                 break;
 114             }
 115             break;
 116
 117         case ArithMul:
 118             handleCommutativity();
 119             break;
 120
 121         case ArithSub:
 122             if (m_node->child2()->isInt32Constant()
 123                 && m_node->isBinaryUseKind(Int32Use)) {
 124                 int32_t value = m_node->child2()->asInt32();
 125                 if (-value != value) {
 126                     m_node->setOp(ArithAdd);
 127                     m_node->child2().setNode(
 128                         m_insertionSet.insertConstant(
 129                             m_nodeIndex, m_node->origin, jsNumber(-value)));
 130                     m_changed = true;
 131                     break;
 132                 }
 133             }
 134             break;
 135
 136         case ArithPow:
 137             if (m_node->child2()->isNumberConstant()) {
 138                 double yOperandValue = m_node->child2()->asNumber();
 139                 if (yOperandValue == 1) {
 140                     convertToIdentityOverChild1();
 141                 } else if (yOperandValue == 0.5) {
 142                     m_insertionSet.insertCheck(m_nodeIndex, m_node);
 143                     m_node->convertToArithSqrt();
 144                     m_changed = true;
 145                 }
 146             }
 147             break;
 148
 149         case ValueRep:
 150         case Int52Rep:
 151         case DoubleRep: {
 152             // This short-circuits circuitous conversions, like ValueRep(DoubleRep(value)) or
 153             // even more complicated things. Like, it can handle a beast like
 154             // ValueRep(DoubleRep(Int52Rep(value))).
 155
 156             // The only speculation that we would do beyond validating that we have a type that
 157             // can be represented a certain way is an Int32 check that would appear on Int52Rep
 158             // nodes. For now, if we see this and the final type we want is an Int52, we use it
 159             // as an excuse not to fold. The only thing we would need is a Int52RepInt32Use kind.
 160             bool hadInt32Check = false;
 161             if (m_node->op() == Int52Rep) {
 162                 if (m_node->child1().useKind() != Int32Use)
 163                     break;
 164                 hadInt32Check = true;
 165             }
 166             for (Node* node = m_node->child1().node(); ; node = node->child1().node()) {
 167                 if (canonicalResultRepresentation(node->result()) ==
 168                     canonicalResultRepresentation(m_node->result())) {
 169                     m_insertionSet.insertCheck(m_nodeIndex, m_node);
 170                     if (hadInt32Check) {
 171                         // FIXME: Consider adding Int52RepInt32Use or even DoubleRepInt32Use,
 172                         // which would be super weird. The latter would only arise in some
 173                         // seriously circuitous conversions.
 174                         if (canonicalResultRepresentation(node->result()) != NodeResultJS)
 175                             break;
 176
 177                         m_insertionSet.insertCheck(
 178                             m_nodeIndex, m_node->origin, Edge(node, Int32Use));
 179                     }
 180                     m_node->child1() = node->defaultEdge();
 181                     m_node->convertToIdentity();
 182                     m_changed = true;
 183                     break;
 184                 }
 185
 186                 switch (node->op()) {
 187                 case Int52Rep:
 188                     if (node->child1().useKind() != Int32Use)
 189                         break;
 190                     hadInt32Check = true;
 191                     continue;
 192
 193                 case DoubleRep:
 194                 case ValueRep:
 195                     continue;
 196
 197                 default:
 198                     break;
 199                 }
 200                 break;
 201             }
 202             break;
 203         }
 204
 205         case Flush: {
 206             ASSERT(m_graph.m_form != SSA);
 207
 208             Node* setLocal = nullptr;
 209             VirtualRegister local = m_node->local();
 210
 211             for (unsigned i = m_nodeIndex; i--;) {
 212                 Node* node = m_block->at(i);
 213                 if (node->op() == SetLocal && node->local() == local) {
 214                     setLocal = node;
 215                     break;
 216                 }
 217                 if (accessesOverlap(m_graph, node, AbstractHeap(Stack, local)))
 218                     break;
 219             }
 220
 221             if (!setLocal)
 222                 break;
 223
 224             // The Flush should become a PhantomLocal at this point. This means that we want the
 225             // local's value during OSR, but we don't care if the value is stored to the stack. CPS
 226             // rethreading can canonicalize PhantomLocals for us.
 227             m_node->convertFlushToPhantomLocal();
 228             m_graph.dethread();
 229             m_changed = true;
 230             break;
 231         }
 232
 233         default:
 234             break;
 235         }
 236     }
 237
 238     void convertToIdentityOverChild(unsigned childIndex)
 239     {
 240         m_insertionSet.insertCheck(m_nodeIndex, m_node);
 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 handleCommutativity()
 257     {
 258         // If the right side is a constant then there is nothing left to do.
 259         if (m_node->child2()->hasConstant())
 260             return;
 261
 262         // This case ensures that optimizations that look for x + const don't also have
 263         // to look for const + x.
 264         if (m_node->child1()->hasConstant()) {
 265             std::swap(m_node->child1(), m_node->child2());
 266             m_changed = true;
 267             return;
 268         }
 269
 270         // This case ensures that CSE is commutativity-aware.
 271         if (m_node->child1().node() > m_node->child2().node()) {
 272             std::swap(m_node->child1(), m_node->child2());
 273             m_changed = true;
 274             return;
 275         }
 276     }
 277
 278     InsertionSet m_insertionSet;
 279     BasicBlock* m_block;
 280     unsigned m_nodeIndex;
 281     Node* m_node;
 282     bool m_changed;
 283 };
 284
 285 bool performStrengthReduction(Graph& graph)
 286 {
 287     SamplingRegion samplingRegion("DFG Strength Reduction Phase");
 288     return runPhase<StrengthReductionPhase>(graph);
 289 }
 290
 291 } } // namespace JSC::DFG
 292
 293 #endif // ENABLE(DFG_JIT)
 294