dfg/DFGDCEPhase.cpp

   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 "DFGDCEPhase.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGBasicBlockInlines.h"
  32 #include "DFGGraph.h"
  33 #include "DFGInsertionSet.h"
  34 #include "DFGPhase.h"
  35 #include "JSCInlines.h"
  36
  37 namespace JSC { namespace DFG {
  38
  39 class DCEPhase : public Phase {
  40 public:
  41     DCEPhase(Graph& graph)
  42         : Phase(graph, "dead code elimination")
  43         , m_insertionSet(graph)
  44     {
  45     }
  46
  47     bool run()
  48     {
  49         ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == SSA);
  50
  51         // First reset the counts to 0 for all nodes.
  52         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
  53             BasicBlock* block = m_graph.block(blockIndex);
  54             if (!block)
  55                 continue;
  56             for (unsigned indexInBlock = block->size(); indexInBlock--;)
  57                 block->at(indexInBlock)->setRefCount(0);
  58             for (unsigned phiIndex = block->phis.size(); phiIndex--;)
  59                 block->phis[phiIndex]->setRefCount(0);
  60         }
  61
  62         // Now find the roots:
  63         // - Nodes that are must-generate.
  64         // - Nodes that are reachable from type checks.
  65         // Set their ref counts to 1 and put them on the worklist.
  66         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
  67             BasicBlock* block = m_graph.block(blockIndex);
  68             if (!block)
  69                 continue;
  70             for (unsigned indexInBlock = block->size(); indexInBlock--;) {
  71                 Node* node = block->at(indexInBlock);
  72                 DFG_NODE_DO_TO_CHILDREN(m_graph, node, findTypeCheckRoot);
  73                 if (!(node->flags() & NodeMustGenerate))
  74                     continue;
  75                 if (!node->postfixRef())
  76                     m_worklist.append(node);
  77             }
  78         }
  79
  80         while (!m_worklist.isEmpty()) {
  81             while (!m_worklist.isEmpty()) {
  82                 Node* node = m_worklist.last();
  83                 m_worklist.removeLast();
  84                 ASSERT(node->shouldGenerate()); // It should not be on the worklist unless it's ref'ed.
  85                 DFG_NODE_DO_TO_CHILDREN(m_graph, node, countEdge);
  86             }
  87
  88             if (m_graph.m_form == SSA) {
  89                 // Find Phi->Upsilon edges, which are represented as meta-data in the
  90                 // Upsilon.
  91                 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
  92                     BasicBlock* block = m_graph.block(blockIndex);
  93                     if (!block)
  94                         continue;
  95                     for (unsigned nodeIndex = block->size(); nodeIndex--;) {
  96                         Node* node = block->at(nodeIndex);
  97                         if (node->op() != Upsilon)
  98                             continue;
  99                         if (node->shouldGenerate())
 100                             continue;
 101                         if (node->phi()->shouldGenerate())
 102                             countNode(node);
 103                     }
 104                 }
 105             }
 106         }
 107
 108         if (m_graph.m_form == SSA) {
 109             Vector<BasicBlock*> depthFirst;
 110             m_graph.getBlocksInDepthFirstOrder(depthFirst);
 111             for (unsigned i = 0; i < depthFirst.size(); ++i)
 112                 fixupBlock(depthFirst[i]);
 113         } else {
 114             RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
 115
 116             for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
 117                 fixupBlock(m_graph.block(blockIndex));
 118
 119             cleanVariables(m_graph.m_arguments);
 120         }
 121
 122         m_graph.m_refCountState = ExactRefCount;
 123
 124         return true;
 125     }
 126
 127 private:
 128     void findTypeCheckRoot(Node*, Edge edge)
 129     {
 130         // We may have an "unproved" untyped use for code that is unreachable. The CFA
 131         // will just not have gotten around to it.
 132         if (edge.willNotHaveCheck())
 133             return;
 134         if (!edge->postfixRef())
 135             m_worklist.append(edge.node());
 136     }
 137
 138     void countNode(Node* node)
 139     {
 140         if (node->postfixRef())
 141             return;
 142         m_worklist.append(node);
 143     }
 144
 145     void countEdge(Node*, Edge edge)
 146     {
 147         // Don't count edges that are already counted for their type checks.
 148         if (edge.willHaveCheck())
 149             return;
 150         countNode(edge.node());
 151     }
 152
 153     void fixupBlock(BasicBlock* block)
 154     {
 155         if (!block)
 156             return;
 157
 158         switch (m_graph.m_form) {
 159         case SSA:
 160             break;
 161
 162         case ThreadedCPS: {
 163             // Clean up variable links for the block. We need to do this before the actual DCE
 164             // because we need to see GetLocals, so we can bypass them in situations where the
 165             // vars-at-tail point to a GetLocal, the GetLocal is dead, but the Phi it points
 166             // to is alive.
 167
 168             for (unsigned phiIndex = 0; phiIndex < block->phis.size(); ++phiIndex) {
 169                 if (!block->phis[phiIndex]->shouldGenerate()) {
 170                     // FIXME: We could actually free nodes here. Except that it probably
 171                     // doesn't matter, since we don't add any nodes after this phase.
 172                     // https://bugs.webkit.org/show_bug.cgi?id=126239
 173                     block->phis[phiIndex--] = block->phis.last();
 174                     block->phis.removeLast();
 175                 }
 176             }
 177
 178             cleanVariables(block->variablesAtHead);
 179             cleanVariables(block->variablesAtTail);
 180             break;
 181         }
 182
 183         default:
 184             RELEASE_ASSERT_NOT_REACHED();
 185             return;
 186         }
 187
 188         // This has to be a forward loop because we are using the insertion set.
 189         for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
 190             Node* node = block->at(indexInBlock);
 191             if (node->shouldGenerate())
 192                 continue;
 193
 194             switch (node->op()) {
 195             case MovHint: {
 196                 // Check if the child is dead. MovHint's child would only be a Phantom
 197                 // if we had just killed it.
 198                 if (node->child1()->op() == Phantom) {
 199                     node->setOpAndDefaultFlags(ZombieHint);
 200                     node->child1() = Edge();
 201                     break;
 202                 }
 203                 break;
 204             }
 205
 206             case ZombieHint: {
 207                 // Currently we assume that DCE runs only once.
 208                 RELEASE_ASSERT_NOT_REACHED();
 209                 break;
 210             }
 211
 212             default: {
 213                 if (node->flags() & NodeHasVarArgs) {
 214                     for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) {
 215                         Edge edge = m_graph.m_varArgChildren[childIdx];
 216
 217                         if (!edge || edge.willNotHaveCheck())
 218                             continue;
 219
 220                         m_insertionSet.insertNode(indexInBlock, SpecNone, Phantom, node->origin, edge);
 221                     }
 222
 223                     node->convertToPhantomUnchecked();
 224                     node->children.reset();
 225                     node->setRefCount(1);
 226                     break;
 227                 }
 228
 229                 node->convertToPhantom();
 230                 eliminateIrrelevantPhantomChildren(node);
 231                 node->setRefCount(1);
 232                 break;
 233             } }
 234         }
 235
 236         m_insertionSet.execute(block);
 237     }
 238
 239     void eliminateIrrelevantPhantomChildren(Node* node)
 240     {
 241         for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
 242             Edge edge = node->children.child(i);
 243             if (!edge)
 244                 continue;
 245             if (edge.willNotHaveCheck())
 246                 node->children.removeEdge(i--);
 247         }
 248     }
 249
 250     template<typename VariablesVectorType>
 251     void cleanVariables(VariablesVectorType& variables)
 252     {
 253         for (unsigned i = variables.size(); i--;) {
 254             Node* node = variables[i];
 255             if (!node)
 256                 continue;
 257             if (node->op() != Phantom && node->shouldGenerate())
 258                 continue;
 259             if (node->op() == GetLocal) {
 260                 node = node->child1().node();
 261
 262                 // FIXME: In the case that the variable is captured, we really want to be able
 263                 // to replace the variable-at-tail with the last use of the variable in the same
 264                 // way that CPS rethreading would do. The child of the GetLocal isn't necessarily
 265                 // the same as what CPS rethreading would do. For example, we may have:
 266                 //
 267                 // a: SetLocal(...) // live
 268                 // b: GetLocal(@a) // live
 269                 // c: GetLocal(@a) // dead
 270                 //
 271                 // When killing @c, the code below will set the variable-at-tail to @a, while CPS
 272                 // rethreading would have set @b. This is a benign bug, since all clients of CPS
 273                 // only use the variable-at-tail of captured variables to get the
 274                 // VariableAccessData and observe that it is in fact captured. But, this feels
 275                 // like it could cause bugs in the future.
 276                 //
 277                 // It's tempting to just dethread and then invoke CPS rethreading, but CPS
 278                 // rethreading fails to preserve exact ref-counts. So we would need a fixpoint.
 279                 // It's probably the case that this fixpoint will be guaranteed to converge after
 280                 // the second iteration (i.e. the second run of DCE will not kill anything and so
 281                 // will not need to dethread), but for now the safest approach is probably just to
 282                 // allow for this tiny bit of sloppiness.
 283                 //
 284                 // Another possible solution would be to simply say that DCE dethreads but then
 285                 // we never rethread before going to the backend. That feels intuitively right
 286                 // because it's unlikely that any of the phases after DCE in the backend rely on
 287                 // ThreadedCPS.
 288                 //
 289                 // https://bugs.webkit.org/show_bug.cgi?id=130115
 290                 ASSERT(
 291                     node->op() == Phi || node->op() == SetArgument
 292                     || node->variableAccessData()->isCaptured());
 293
 294                 if (node->shouldGenerate()) {
 295                     variables[i] = node;
 296                     continue;
 297                 }
 298             }
 299             variables[i] = 0;
 300         }
 301     }
 302
 303     Vector<Node*, 128> m_worklist;
 304     InsertionSet m_insertionSet;
 305 };
 306
 307 bool performDCE(Graph& graph)
 308 {
 309     SamplingRegion samplingRegion("DFG DCE Phase");
 310     return runPhase<DCEPhase>(graph);
 311 }
 312
 313 } } // namespace JSC::DFG
 314
 315 #endif // ENABLE(DFG_JIT)
 316