dfg/DFGRedundantPhiEliminationPhase.cpp

   1 /*
   2  * Copyright (C) 2012 Intel Corporation. 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 "DFGRedundantPhiEliminationPhase.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGGraph.h"
  32
  33 namespace JSC { namespace DFG {
  34
  35 class RedundantPhiEliminationPhase : public Phase {
  36 public:
  37     RedundantPhiEliminationPhase(Graph& graph)
  38         : Phase(graph, "redundant phi elimination")
  39     {
  40     }
  41
  42     void run()
  43     {
  44         bool changed = false;
  45         do {
  46             changed = fixupPhis();
  47         } while (changed);
  48
  49         updateBlockVariableInformation();
  50
  51         // Update the Phi references from non-Phi nodes, e.g., the GetLocals.
  52         for (NodeIndex index = 0; index < m_graph.size(); ++index) {
  53             Node& node = m_graph[index];
  54
  55             if (!node.shouldGenerate())
  56                 continue;
  57
  58             switch (node.op()) {
  59             case GetLocal:
  60                 replacePhiChild(node, 0);
  61                 break;
  62             default:
  63                 break;
  64             }
  65         }
  66
  67     }
  68
  69 private:
  70     NodeIndex getRedundantReplacement(NodeIndex phi)
  71     {
  72         NodeIndex child1 = m_graph[phi].child1().indexUnchecked();
  73         NodeIndex candidate = child1 == phi ? NoNode : child1;
  74
  75         NodeIndex child2 = m_graph[phi].child2().indexUnchecked();
  76         if (candidate != NoNode) {
  77             if (child2 != NoNode && child2 != candidate && child2 != phi)
  78                 return NoNode;
  79         } else if (child2 != phi)
  80             candidate = child2;
  81
  82         NodeIndex child3 = m_graph[phi].child3().indexUnchecked();
  83         if (candidate != NoNode) {
  84             if (child3 != NoNode && child3 != candidate && child3 != phi)
  85                 return NoNode;
  86         } else if (child3 != phi)
  87             candidate = child3;
  88
  89         return candidate;
  90     }
  91
  92     bool replacePhiChild(Node& node, unsigned childIndex)
  93     {
  94         ASSERT(childIndex < 3);
  95
  96         bool replaced = false;
  97         NodeIndex child = node.children.child(childIndex).indexUnchecked();
  98         if (child != NoNode && m_graph[child].op() == Phi) {
  99             NodeIndex childReplacement = getRedundantReplacement(child);
 100             if (childReplacement != NoNode) {
 101                 node.children.child(childIndex).setIndex(childReplacement);
 102                 replaced = true;
 103                 if (node.refCount()) {
 104                     m_graph[childReplacement].ref();
 105                     m_graph.deref(child);
 106                 }
 107             }
 108         }
 109         return replaced;
 110     }
 111
 112     bool fixupPhis()
 113     {
 114         bool changed = false;
 115
 116         for (BlockIndex block = 0; block < m_graph.m_blocks.size(); ++block) {
 117             Vector<NodeIndex>& phis = m_graph.m_blocks[block]->phis;
 118
 119             for (size_t i = 0; i < phis.size(); ++i) {
 120                 NodeIndex phi = phis[i];
 121                 Node& phiNode = m_graph[phi];
 122
 123                 changed |= (replacePhiChild(phiNode, 0) && phiNode.refCount());
 124                 changed |= (replacePhiChild(phiNode, 1) && phiNode.refCount());
 125                 changed |= (replacePhiChild(phiNode, 2) && phiNode.refCount());
 126             }
 127         }
 128
 129         return changed;
 130     }
 131
 132     void updateBlockVariableInformation()
 133     {
 134         // Redundant Phi nodes are eliminated, we need to update
 135         // the variable information if it references them.
 136         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
 137             BasicBlock* basicBlock = m_graph.m_blocks[blockIndex].get();
 138
 139             for (size_t arg = 0; arg < basicBlock->variablesAtHead.numberOfArguments(); ++arg) {
 140                 NodeIndex nodeIndex = basicBlock->variablesAtHead.argument(arg);
 141                 if (nodeIndex != NoNode && m_graph[nodeIndex].op() == Phi && !m_graph[nodeIndex].refCount()) {
 142                     NodeIndex replacement = getRedundantReplacement(nodeIndex);
 143                     if (replacement != NoNode) {
 144                         // This argument must be unused in this block.
 145                         ASSERT(basicBlock->variablesAtTail.argument(arg) == nodeIndex);
 146                         basicBlock->variablesAtHead.argument(arg) = replacement;
 147                         basicBlock->variablesAtTail.argument(arg) = replacement;
 148                     }
 149                 }
 150             }
 151
 152             for (size_t local = 0; local < basicBlock->variablesAtHead.numberOfLocals(); ++local) {
 153                 NodeIndex nodeIndex = basicBlock->variablesAtHead.local(local);
 154                 if (nodeIndex != NoNode && m_graph[nodeIndex].op() == Phi && !m_graph[nodeIndex].refCount()) {
 155                     NodeIndex replacement = getRedundantReplacement(nodeIndex);
 156                     if (replacement != NoNode) {
 157                         // This local variable must be unused in this block.
 158                         ASSERT(basicBlock->variablesAtTail.local(local) == nodeIndex);
 159                         basicBlock->variablesAtHead.local(local) = replacement;
 160                         basicBlock->variablesAtTail.local(local) = replacement;
 161                     }
 162                 }
 163             }
 164         }
 165     }
 166
 167 };
 168
 169 void performRedundantPhiElimination(Graph& graph)
 170 {
 171     runPhase<RedundantPhiEliminationPhase>(graph);
 172 }
 173
 174 } } // namespace JSC::DFG
 175
 176 #endif // ENABLE(DFG_JIT)