dfg/DFGDCEPhase.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 "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 "Operations.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     {
  44     }
  45
  46     bool run()
  47     {
  48         // First reset the counts to 0 for all nodes.
  49         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
  50             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
  51             if (!block)
  52                 continue;
  53             for (unsigned indexInBlock = block->size(); indexInBlock--;)
  54                 block->at(indexInBlock)->setRefCount(0);
  55             for (unsigned phiIndex = block->phis.size(); phiIndex--;)
  56                 block->phis[phiIndex]->setRefCount(0);
  57         }
  58
  59         // Now find the roots:
  60         // - Nodes that are must-generate.
  61         // - Nodes that are reachable from type checks.
  62         // Set their ref counts to 1 and put them on the worklist.
  63         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
  64             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
  65             if (!block)
  66                 continue;
  67             for (unsigned indexInBlock = block->size(); indexInBlock--;) {
  68                 Node* node = block->at(indexInBlock);
  69                 DFG_NODE_DO_TO_CHILDREN(m_graph, node, findTypeCheckRoot);
  70                 if (!(node->flags() & NodeMustGenerate))
  71                     continue;
  72                 if (!node->postfixRef())
  73                     m_worklist.append(node);
  74             }
  75         }
  76
  77         while (!m_worklist.isEmpty()) {
  78             Node* node = m_worklist.last();
  79             m_worklist.removeLast();
  80             ASSERT(node->shouldGenerate()); // It should not be on the worklist unless it's ref'ed.
  81             DFG_NODE_DO_TO_CHILDREN(m_graph, node, countEdge);
  82         }
  83
  84         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
  85             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
  86             if (!block)
  87                 continue;
  88
  89             InsertionSet insertionSet(m_graph);
  90
  91             for (unsigned indexInBlock = block->size(); indexInBlock--;) {
  92                 Node* node = block->at(indexInBlock);
  93                 if (node->shouldGenerate())
  94                     continue;
  95
  96                 switch (node->op()) {
  97                 case SetLocal: {
  98                     if (node->child1().isProved() || node->child1().useKind() == UntypedUse) {
  99                         // Consider the possibility that UInt32ToNumber is dead but its
 100                         // child isn't; if so then we should MovHint the child.
 101                         if (!node->child1()->shouldGenerate()
 102                             && node->child1()->op() == UInt32ToNumber)
 103                             node->child1() = node->child1()->child1();
 104
 105                         if (!node->child1()->shouldGenerate()) {
 106                             node->setOpAndDefaultFlags(ZombieHint);
 107                             node->child1() = Edge();
 108                             break;
 109                         }
 110                         node->setOpAndDefaultFlags(MovHint);
 111                         break;
 112                     }
 113                     node->setOpAndDefaultFlags(MovHintAndCheck);
 114                     node->setRefCount(1);
 115                     break;
 116                 }
 117
 118                 case GetLocal:
 119                 case SetArgument: {
 120                     // Leave them as not shouldGenerate.
 121                     break;
 122                 }
 123
 124                 default: {
 125                     if (node->flags() & NodeHasVarArgs) {
 126                         for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) {
 127                             Edge edge = m_graph.m_varArgChildren[childIdx];
 128
 129                             if (!edge || edge.isProved() || edge.useKind() == UntypedUse)
 130                                 continue;
 131
 132                             insertionSet.insertNode(indexInBlock, SpecNone, Phantom, node->codeOrigin, edge);
 133                         }
 134
 135                         node->convertToPhantomUnchecked();
 136                         node->children.reset();
 137                         node->setRefCount(1);
 138                         break;
 139                     }
 140
 141                     node->convertToPhantom();
 142                     eliminateIrrelevantPhantomChildren(node);
 143                     node->setRefCount(1);
 144                     break;
 145                 } }
 146             }
 147
 148             insertionSet.execute(block);
 149         }
 150
 151         m_graph.m_refCountState = ExactRefCount;
 152
 153         return true;
 154     }
 155
 156 private:
 157     void findTypeCheckRoot(Node*, Edge edge)
 158     {
 159         // We may have an "unproved" untyped use for code that is unreachable. The CFA
 160         // will just not have gotten around to it.
 161         if (edge.isProved() || edge.useKind() == UntypedUse)
 162             return;
 163         if (!edge->postfixRef())
 164             m_worklist.append(edge.node());
 165     }
 166
 167     void countEdge(Node*, Edge edge)
 168     {
 169         // Don't count edges that are already counted for their type checks.
 170         if (!(edge.isProved() || edge.useKind() == UntypedUse))
 171             return;
 172
 173         if (edge->postfixRef())
 174             return;
 175         m_worklist.append(edge.node());
 176     }
 177
 178     void eliminateIrrelevantPhantomChildren(Node* node)
 179     {
 180         for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
 181             Edge edge = node->children.child(i);
 182             if (!edge)
 183                 continue;
 184             if (edge.isProved() || edge.useKind() == UntypedUse)
 185                 node->children.removeEdge(i--);
 186         }
 187     }
 188
 189     Vector<Node*, 128> m_worklist;
 190 };
 191
 192 bool performDCE(Graph& graph)
 193 {
 194     SamplingRegion samplingRegion("DFG DCE Phase");
 195     return runPhase<DCEPhase>(graph);
 196 }
 197
 198 } } // namespace JSC::DFG
 199
 200 #endif // ENABLE(DFG_JIT)
 201