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 "DFGLivenessAnalysisPhase.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 37namespace JSC { namespace DFG { 38 39class LivenessAnalysisPhase : public Phase { 40public: 41 LivenessAnalysisPhase(Graph& graph) 42 : Phase(graph, "liveness analysis") 43 { 44 } 45 46 bool run() 47 { 48 ASSERT(m_graph.m_form == SSA); 49 50 // Liveness is a backwards analysis; the roots are the blocks that 51 // end in a terminal (Return/Throw/ThrowReferenceError). For now, we 52 // use a fixpoint formulation since liveness is a rapid analysis with 53 // convergence guaranteed after O(connectivity). 54 55 // Start by assuming that everything is dead. 56 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) { 57 BasicBlock* block = m_graph.block(blockIndex); 58 if (!block) 59 continue; 60 block->ssa->liveAtHead.clear(); 61 block->ssa->liveAtTail.clear(); 62 } 63 64 do { 65 m_changed = false; 66 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) 67 process(blockIndex); 68 } while (m_changed); 69 70 if (!m_graph.block(0)->ssa->liveAtHead.isEmpty()) { 71 startCrashing(); 72 dataLog( 73 "Bad liveness analysis result: live at root is not empty: ", 74 nodeListDump(m_graph.block(0)->ssa->liveAtHead), "\n"); 75 dataLog("IR at time of error:\n"); 76 m_graph.dump(); 77 CRASH(); 78 } 79 80 return true; 81 } 82 83private: 84 void process(BlockIndex blockIndex) 85 { 86 BasicBlock* block = m_graph.block(blockIndex); 87 if (!block) 88 return; 89 90 // FIXME: It's likely that this can be improved, for static analyses that use 91 // HashSets. https://bugs.webkit.org/show_bug.cgi?id=118455 92 m_live = block->ssa->liveAtTail; 93 94 for (unsigned nodeIndex = block->size(); nodeIndex--;) { 95 Node* node = block->at(nodeIndex); 96 97 // Given an Upsilon: 98 // 99 // n: Upsilon(@x, ^p) 100 // 101 // We say that it def's @p and @n and uses @x. 102 // 103 // Given a Phi: 104 // 105 // p: Phi() 106 // 107 // We say nothing. It's neither a use nor a def. 108 // 109 // Given a node: 110 // 111 // n: Thingy(@a, @b, @c) 112 // 113 // We say that it def's @n and uses @a, @b, @c. 114 115 switch (node->op()) { 116 case Upsilon: { 117 Node* phi = node->phi(); 118 m_live.remove(phi); 119 m_live.remove(node); 120 m_live.add(node->child1().node()); 121 break; 122 } 123 124 case Phi: { 125 break; 126 } 127 128 default: 129 m_live.remove(node); 130 DFG_NODE_DO_TO_CHILDREN(m_graph, node, addChildUse); 131 break; 132 } 133 } 134 135 if (m_live == block->ssa->liveAtHead) 136 return; 137 138 m_changed = true; 139 block->ssa->liveAtHead = m_live; 140 for (unsigned i = block->predecessors.size(); i--;) 141 block->predecessors[i]->ssa->liveAtTail.add(m_live.begin(), m_live.end()); 142 } 143 144 void addChildUse(Node*, Edge& edge) 145 { 146 addChildUse(edge); 147 } 148 149 void addChildUse(Edge& edge) 150 { 151 edge.setKillStatus(m_live.add(edge.node()).isNewEntry ? DoesKill : DoesNotKill); 152 } 153 154 bool m_changed; 155 HashSet<Node*> m_live; 156}; 157 158bool performLivenessAnalysis(Graph& graph) 159{ 160 SamplingRegion samplingRegion("DFG Liveness Analysis Phase"); 161 return runPhase<LivenessAnalysisPhase>(graph); 162} 163 164} } // namespace JSC::DFG 165 166#endif // ENABLE(DFG_JIT) 167 168