Changeset 203921 in webkit for trunk/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp
- Timestamp:
- Jul 29, 2016, 1:58:35 PM (9 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp
r198364 r203921 1 1 /* 2 * Copyright (C) 2013, 2015 Apple Inc. All rights reserved.2 * Copyright (C) 2013, 2015-2016 Apple Inc. All rights reserved. 3 3 * 4 4 * Redistribution and use in source and binary forms, with or without … … 30 30 31 31 #include "DFGBasicBlockInlines.h" 32 #include "DFGBlockMapInlines.h" 32 33 #include "DFGGraph.h" 33 34 #include "DFGInsertionSet.h" 34 35 #include "DFGPhase.h" 35 36 #include "JSCInlines.h" 37 #include <wtf/BitVector.h> 38 #include <wtf/IndexSparseSet.h> 36 39 37 40 namespace JSC { namespace DFG { … … 41 44 LivenessAnalysisPhase(Graph& graph) 42 45 : Phase(graph, "liveness analysis") 43 { 44 } 45 46 , m_dirtyBlocks(m_graph.numBlocks()) 47 , m_liveAtHead(m_graph) 48 , m_liveAtTail(m_graph) 49 , m_workset(graph.maxNodeCount() - 1) 50 { 51 } 52 46 53 bool run() 47 54 { 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--;) { 55 // Start with all valid block dirty. 56 BlockIndex numBlock = m_graph.numBlocks(); 57 m_dirtyBlocks.ensureSize(numBlock); 58 for (BlockIndex blockIndex = 0; blockIndex < numBlock; ++blockIndex) { 59 if (m_graph.block(blockIndex)) 60 m_dirtyBlocks.quickSet(blockIndex); 61 } 62 63 // Fixpoint until we do not add any new live values at tail. 64 bool changed; 65 do { 66 changed = false; 67 68 for (BlockIndex blockIndex = numBlock; blockIndex--;) { 69 if (!m_dirtyBlocks.quickClear(blockIndex)) 70 continue; 71 72 changed |= processBlock(blockIndex); 73 } 74 } while (changed); 75 76 // Update the per-block node list for live and tail. 77 for (BlockIndex blockIndex = numBlock; blockIndex--;) { 57 78 BasicBlock* block = m_graph.block(blockIndex); 58 79 if (!block) 59 80 continue; 60 block->ssa->liveAtTailIsDirty = true; 61 block->ssa->liveAtHead.clear();62 block->ssa->liveAtTail.clear();63 }64 65 do {66 m_changed = false;67 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;)68 process(blockIndex);69 } while (m_changed);70 71 if (!m_graph.block(0)->ssa->liveAtHead.isEmpty()) {72 DFG_CRASH(73 m_graph, nullptr,74 toCString(75 "Bad liveness analysis result: live at root is not empty: ",76 nodeListDump(m_graph.block(0)->ssa->liveAtHead)).data());77 } 78 81 82 { 83 const auto& liveAtHeadIndices = m_liveAtHead[blockIndex]; 84 Vector<Node*>& liveAtHead = block->ssa->liveAtHead; 85 liveAtHead.resize(0); 86 liveAtHead.reserveCapacity(liveAtHeadIndices.size()); 87 for (unsigned index : liveAtHeadIndices) 88 liveAtHead.uncheckedAppend(m_graph.nodeAt(index)); 89 } 90 { 91 const auto& liveAtTailIndices = m_liveAtTail[blockIndex]; 92 Vector<Node*>& liveAtTail = block->ssa->liveAtTail; 93 liveAtTail.resize(0); 94 liveAtTail.reserveCapacity(liveAtTailIndices.size()); 95 for (unsigned index : m_liveAtTail[blockIndex]) 96 liveAtTail.uncheckedAppend(m_graph.nodeAt(index)); 97 } 98 } 99 79 100 return true; 80 101 } 81 102 82 103 private: 83 void process(BlockIndex blockIndex)104 bool processBlock(BlockIndex blockIndex) 84 105 { 85 106 BasicBlock* block = m_graph.block(blockIndex); 86 if (!block) 87 return; 88 89 if (!block->ssa->liveAtTailIsDirty) 90 return; 91 block->ssa->liveAtTailIsDirty = false; 92 93 m_live = block->ssa->liveAtTail; 107 ASSERT_WITH_MESSAGE(block, "Only dirty blocks needs updates. A null block should never be dirty."); 108 109 m_workset.clear(); 110 for (unsigned index : m_liveAtTail[blockIndex]) 111 m_workset.add(index); 112 94 113 for (unsigned nodeIndex = block->size(); nodeIndex--;) { 95 114 Node* node = block->at(nodeIndex); 96 115 97 116 // Given an Upsilon: 98 117 // … … 115 134 switch (node->op()) { 116 135 case Upsilon: { 136 ASSERT_WITH_MESSAGE(!m_workset.contains(node->index()), "Upsilon should not be used as defs by other nodes."); 137 117 138 Node* phi = node->phi(); 118 m_live.remove(phi); 119 m_live.remove(node); 120 m_live.add(node->child1().node()); 139 m_workset.remove(phi->index()); 140 m_workset.add(node->child1()->index()); 121 141 break; 122 142 } 123 124 143 case Phi: { 125 144 break; 126 145 } 127 128 146 default: 129 m_ live.remove(node);147 m_workset.remove(node->index()); 130 148 DFG_NODE_DO_TO_CHILDREN(m_graph, node, addChildUse); 131 149 break; 132 150 } 133 151 } 134 135 for (Node* node : m_live) { 136 if (!block->ssa->liveAtHead.contains(node)) { 137 m_changed = true; 138 for (unsigned i = block->predecessors.size(); i--;) { 139 BasicBlock* predecessor = block->predecessors[i]; 140 if (predecessor->ssa->liveAtTail.add(node).isNewEntry) 141 predecessor->ssa->liveAtTailIsDirty = true; 152 153 // Update live at head. 154 auto& liveAtHead = m_liveAtHead[blockIndex]; 155 if (m_workset.size() == liveAtHead.size()) 156 return false; 157 158 for (unsigned liveIndexAtHead : liveAtHead) 159 m_workset.remove(liveIndexAtHead); 160 ASSERT(!m_workset.isEmpty()); 161 162 liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size()); 163 for (unsigned newValue : m_workset) 164 liveAtHead.uncheckedAppend(newValue); 165 166 bool changedPredecessor = false; 167 for (BasicBlock* predecessor : block->predecessors) { 168 auto& liveAtTail = m_liveAtTail[predecessor]; 169 for (unsigned newValue : m_workset) { 170 if (liveAtTail.add(newValue)) { 171 if (!m_dirtyBlocks.quickSet(predecessor->index)) 172 changedPredecessor = true; 142 173 } 143 174 } 144 175 } 145 block->ssa->liveAtHead = WTFMove(m_live); 146 } 147 148 void addChildUse(Node*, Edge& edge) 149 { 150 addChildUse(edge); 151 } 152 153 void addChildUse(Edge& edge) 154 { 155 edge.setKillStatus(m_live.add(edge.node()).isNewEntry ? DoesKill : DoesNotKill); 156 } 157 158 bool m_changed; 159 HashSet<Node*> m_live; 176 return changedPredecessor; 177 } 178 179 ALWAYS_INLINE void addChildUse(Node*, Edge& edge) 180 { 181 bool newEntry = m_workset.add(edge->index()); 182 edge.setKillStatus(newEntry ? DoesKill : DoesNotKill); 183 } 184 185 // Blocks with new live values at tail. 186 BitVector m_dirtyBlocks; 187 188 // Live values per block edge. 189 BlockMap<Vector<unsigned, 0, UnsafeVectorOverflow, 1>> m_liveAtHead; 190 BlockMap<HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>> m_liveAtTail; 191 192 // Single sparse set allocated once and used by every basic block. 193 IndexSparseSet<UnsafeVectorOverflow> m_workset; 160 194 }; 161 195
Note:
See TracChangeset
for help on using the changeset viewer.