Changeset 189126 in webkit
- Timestamp:
- Aug 28, 2015 3:38:41 PM (9 years ago)
- Location:
- trunk
- Files:
-
- 2 added
- 8 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/JavaScriptCore/ChangeLog
r189124 r189126 1 2015-08-28 Filip Pizlo <fpizlo@apple.com> 2 3 LICM should be sound even if the CFG has changed 4 https://bugs.webkit.org/show_bug.cgi?id=148259 5 6 Reviewed by Benjamin Poulain. 7 8 Prior to this change, LICM expected a certain CFG shape around a loop: broken critical edges, 9 a pre-header, and the pre-header's terminal has exitOK. LICM would either crash on an 10 assertion, or generate code that fails validation, if these conditions weren't met. 11 12 The broken critical edge assumption is fine; so far we are assuming that SSA means broken 13 critical edges. We may revisit this, but we don't have to right now. 14 15 The other assumptions are not fine, because it's hard to guarantee that every phase will 16 preserve the presence of pre-headers. Even if we required that pre-headers are regenerated 17 before LICM, that regeneration wouldn't be guaranteed to create pre-headers that have exitOK at 18 the terminal. That's because once in SSA, the loop header probably has exitOK=false at the 19 head because of Phi's. Pre-header creation has no choice but to use the Node::origin from the 20 loop header, which means creating a pre-header that has exitOK=false. Regardless of whether 21 that's a fixable problem, it seems that our best short-term approach is just to be defensive 22 and turn undesirable pathologies into performance bugs and not crashes. 23 24 For the foreseeable future, once pre-headers are created they will probably not be removed. Our 25 current CFG simplification phase doesn't have a rule for removing pre-headers (since it doesn't 26 have any jump threading). So, it wouldn't be profitable to put effort towards reneration of 27 pre-headers for LICM's benefit. 28 29 Also, we cannot guarantee that some sequence of CFG transformations will not create a loop that 30 doesn't have a pre-header. This would be super rare. But you could imagine that some program 31 has control flow encoded using relooping (like 32 https://github.com/kripken/Relooper/blob/master/paper.pdf). If that happens, our compiler will 33 probably incrementally discover the "original" CFG. That may happen only after SSA conversion, 34 and so after pre-header generation. This is super unlikely for a bunch of reasons, but it 35 *could* happen. 36 37 So, this patch just makes sure that if pre-headers are missing or cannot be exited from, LICM 38 will simply avoid hoisting out of that block. At some point later, we can worry about a more 39 comprehensive solution to the pre-header problem. That's covered by this bug: 40 https://bugs.webkit.org/show_bug.cgi?id=148586 41 42 * dfg/DFGLICMPhase.cpp: 43 (JSC::DFG::LICMPhase::run): 44 (JSC::DFG::LICMPhase::attemptHoist): 45 * dfg/DFGPlan.cpp: 46 (JSC::DFG::Plan::compileInThreadImpl): 47 * runtime/Options.h: 48 * tests/stress/licm-no-pre-header.js: Added. 49 (foo): 50 * tests/stress/licm-pre-header-cannot-exit.js: Added. 51 (foo): 52 1 53 2015-08-28 Yusuke Suzuki <utatane.tea@gmail.com> 2 54 -
trunk/Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp
r188979 r189126 47 47 bool run() 48 48 { 49 // FIXME: We should make this work in SSA. https://bugs.webkit.org/show_bug.cgi?id=148260 50 DFG_ASSERT(m_graph, nullptr, m_graph.m_form != SSA); 51 49 52 const bool extremeLogging = false; 50 53 -
trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
r189070 r189126 47 47 struct LoopData { 48 48 LoopData() 49 : preHeader( 0)49 : preHeader(nullptr) 50 50 { 51 51 } … … 113 113 const NaturalLoop& loop = m_graph.m_naturalLoops.loop(loopIndex); 114 114 LoopData& data = m_data[loop.index()]; 115 115 116 for ( 116 117 const NaturalLoop* outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(loop); … … 120 121 121 122 BasicBlock* header = loop.header(); 122 BasicBlock* preHeader = 0; 123 BasicBlock* preHeader = nullptr; 124 unsigned numberOfPreHeaders = 0; // We're cool if this is 1. 125 126 // This is guaranteed because we expect the CFG not to have unreachable code. Therefore, a 127 // loop header must have a predecessor. (Also, we don't allow the root block to be a loop, 128 // which cuts out the one other way of having a loop header with only one predecessor.) 129 DFG_ASSERT(m_graph, header->at(0), header->predecessors.size() > 1); 130 123 131 for (unsigned i = header->predecessors.size(); i--;) { 124 132 BasicBlock* predecessor = header->predecessors[i]; 125 133 if (m_graph.m_dominators.dominates(header, predecessor)) 126 134 continue; 127 DFG_ASSERT(m_graph, nullptr, !preHeader || preHeader == predecessor); 135 128 136 preHeader = predecessor; 129 } 130 137 ++numberOfPreHeaders; 138 } 139 140 // We need to validate the pre-header. There are a bunch of things that could be wrong 141 // about it: 142 // 143 // - There might be more than one. This means that pre-header creation either did not run, 144 // or some CFG transformation destroyed the pre-headers. 145 // 146 // - It may not be legal to exit at the pre-header. That would be a real bummer. Currently, 147 // LICM assumes that it can always hoist checks. See 148 // https://bugs.webkit.org/show_bug.cgi?id=148545. Though even with that fixed, we anyway 149 // would need to check if it's OK to exit at the pre-header since if we can't then we 150 // would have to restrict hoisting to non-exiting nodes. 151 152 if (numberOfPreHeaders != 1) 153 continue; 154 155 // This is guaranteed because the header has multiple predecessors and critical edges are 156 // broken. Therefore the predecessors must all have one successor, which implies that they 157 // must end in a Jump. 131 158 DFG_ASSERT(m_graph, preHeader->terminal(), preHeader->terminal()->op() == Jump); 132 133 // We should validate the pre-header. This currently assumes that it's valid to OSR exit at 134 // the Jump of the pre-header. That may not always be the case, like if we lowered a Node 135 // that was ExitInvalid to a loop. This phase should somehow defend against this - at the 136 // very least with assertions, if not with something better (like only hoisting things that 137 // cannot exit). 138 // FIXME: https://bugs.webkit.org/show_bug.cgi?id=148259 159 160 if (!preHeader->terminal()->origin.exitOK) 161 continue; 139 162 140 163 data.preHeader = preHeader; … … 147 170 // - The node doesn't write anything. 148 171 // - The node doesn't read anything that the loop writes. 172 // - The preHeader is valid (i.e. it passed the validation above). 149 173 // - The preHeader's state at tail makes the node safe to execute. 150 174 // - The loop's children all belong to nodes that strictly dominate the loop header. … … 206 230 Node* node = nodeRef; 207 231 LoopData& data = m_data[loop->index()]; 232 233 if (!data.preHeader) { 234 if (verbose) 235 dataLog(" Not hoisting ", node, " because the pre-header is invalid.\n"); 236 return false; 237 } 208 238 209 239 if (!data.preHeader->cfaDidFinish) { -
trunk/Source/JavaScriptCore/dfg/DFGLoopPreHeaderCreationPhase.cpp
r189013 r189126 40 40 BasicBlock* createPreHeader(Graph& graph, BlockInsertionSet& insertionSet, BasicBlock* block) 41 41 { 42 // FIXME: If we run this utility on SSA IR, then we may end up with a bizarre arrangement of 43 // Upsilons and Phis, like: 44 // 45 // BB#1: 46 // Upsilon(@a, ^p) 47 // Jump(#3) 48 // 49 // BB#2: 50 // Upsilon(@b, ^p) 51 // Jump(#3) 52 // 53 // BB#3: 54 // Jump(#4) 55 // 56 // BB#4: 57 // p: Phi() 58 // 59 // Notice how the Upsilons are not in the predecessor of the Phi anymore. It's not clear if this 60 // would be bad. Probably not, but it's weird anyway. We should add a validation rule, and we 61 // should implement a Upsilon/Phi canonicalization that handles this by calling into the 62 // SSACalculator and treating the Upsilons as Defs and rebuilding the Phis from scratch. 63 // 64 // https://bugs.webkit.org/show_bug.cgi?id=148587 65 42 66 // Don't bother to preserve execution frequencies for now. 43 67 BasicBlock* preHeader = insertionSet.insertBefore(block, PNaN); 68 69 // FIXME: It would be great if we put some effort into enabling exitOK at this origin, if it 70 // happens to be unset. It might not be set because the loop header (i.e. "block") has Phis in it. 71 // Phis have to have exitOK=false. There are a few ways to try to set exitOK: 72 // 73 // - Regenerate an exit origin by proving that we are at an exit origin boundary. If all of the 74 // predecessors' terminals have different exit origins than the exit origin of head of block, 75 // then we can leverage the assumption that exit origin boundaries can always exit. We could 76 // extend this further, and say that we will set exitOK even if a predecessor's terminal has the 77 // same exit origin, but so long it hadn't done anything that clobbers exit since the start of 78 // the origin. 79 // 80 // - Analyze the Phi's and MovHint's at the head of block. If prior to the ExitOK there are only 81 // Phi's and MovHint's, we could "roll them back" by proving that for each of the MovHints, the 82 // referenced Phi has a child that dominates the pre-header, and that child is the node that is 83 // OSR-available at the local being MovHinted. 84 // 85 // Note that there are some obviously wrong ways to try to set exitOK. For example, we cannot 86 // simply use the origin of our predecessors, since in bytecode that could be *any* kind of 87 // instruction. It may not even be a control flow construct, if we had lowered some non-control 88 // bytecode operation into DFG IR that has control flow. Hence, we really do need to try to use the 89 // origin of the head of the loop header. 90 // 91 // https://bugs.webkit.org/show_bug.cgi?id=148586 44 92 preHeader->appendNode( 45 93 graph, SpecNone, Jump, block->at(0)->origin, OpInfo(block)); -
trunk/Source/JavaScriptCore/dfg/DFGPlan.cpp
r186985 r189126 375 375 performCleanUp(dfg); // Reduce the graph size a bit. 376 376 performCriticalEdgeBreaking(dfg); 377 performLoopPreHeaderCreation(dfg); 377 if (Options::createPreHeaders()) 378 performLoopPreHeaderCreation(dfg); 378 379 performCPSRethreading(dfg); 379 380 performSSAConversion(dfg); -
trunk/Source/JavaScriptCore/runtime/Options.h
r188752 r189126 196 196 v(unsigned, frequentCallThreshold, 2, nullptr) \ 197 197 v(double, minimumCallToKnownRate, 0.51, nullptr) \ 198 v(bool, createPreHeaders, true, nullptr) \ 198 199 v(bool, enableMovHintRemoval, true, nullptr) \ 199 200 v(bool, enableObjectAllocationSinking, true, nullptr) \ -
trunk/Tools/ChangeLog
r189125 r189126 1 2015-08-28 Filip Pizlo <fpizlo@apple.com> 2 3 LICM should be sound even if the CFG has changed 4 https://bugs.webkit.org/show_bug.cgi?id=148259 5 6 Reviewed by Benjamin Poulain. 7 8 Add a utility for creating tests that set some uncommon option. 9 10 * Scripts/run-jsc-stress-tests: 11 1 12 2015-08-28 Brent Fulgham <bfulgham@apple.com> 2 13 -
trunk/Tools/Scripts/run-jsc-stress-tests
r188767 r189126 763 763 end 764 764 765 def runMiscNoCJITTest(*options) 766 run("misc-no-cjit", *(NO_CJIT_OPTIONS + options)) 767 end 768 769 def runMiscFTLNoCJITTest(*options) 770 run("misc-ftl-no-cjit", *(FTL_OPTIONS + NO_CJIT_OPTIONS + options)) 771 end 772 765 773 def defaultRun 766 774 runDefault
Note: See TracChangeset
for help on using the changeset viewer.