DFG::StoreBarrierInsertionPhase should assume that any epoch increment may make objec...
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGStoreBarrierInsertionPhase.cpp
1 /*
2  * Copyright (C) 2015-2016 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. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "DFGStoreBarrierInsertionPhase.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGAbstractInterpreterInlines.h"
32 #include "DFGBlockMapInlines.h"
33 #include "DFGDoesGC.h"
34 #include "DFGGraph.h"
35 #include "DFGInPlaceAbstractState.h"
36 #include "DFGInsertionSet.h"
37 #include "DFGPhase.h"
38 #include "JSCInlines.h"
39 #include <wtf/CommaPrinter.h>
40 #include <wtf/HashSet.h>
41
42 namespace JSC { namespace DFG {
43
44 namespace {
45
46 bool verbose = false;
47
48 enum class PhaseMode {
49     // Does only a local analysis for store barrier insertion and assumes that pointers live
50     // from predecessor blocks may need barriers. Assumes CPS conventions. Does not use AI for
51     // eliminating store barriers, but does a best effort to eliminate barriers when you're
52     // storing a non-cell value by using Node::result() and by looking at constants. The local
53     // analysis is based on GC epochs, so it will eliminate a lot of locally redundant barriers.
54     Fast,
55         
56     // Does a global analysis for store barrier insertion. Reuses the GC-epoch-based analysis
57     // used by Fast, but adds a conservative merge rule for propagating information from one
58     // block to the next. This will ensure for example that if a value V coming from multiple
59     // predecessors in B didn't need any more barriers at the end of each predecessor (either
60     // because it was the last allocated object in that predecessor or because it just had a
61     // barrier executed), then until we hit another GC point in B, we won't need another barrier
62     // on V. Uses AI for eliminating barriers when we know that the value being stored is not a
63     // cell. Assumes SSA conventions.
64     Global
65 };
66
67 template<PhaseMode mode>
68 class StoreBarrierInsertionPhase : public Phase {
69 public:
70     StoreBarrierInsertionPhase(Graph& graph)
71         : Phase(graph, mode == PhaseMode::Fast ? "fast store barrier insertion" : "global store barrier insertion")
72         , m_insertionSet(graph)
73     {
74     }
75     
76     bool run()
77     {
78         if (verbose) {
79             dataLog("Starting store barrier insertion:\n");
80             m_graph.dump();
81         }
82         
83         switch (mode) {
84         case PhaseMode::Fast: {
85             DFG_ASSERT(m_graph, nullptr, m_graph.m_form != SSA);
86             
87             m_graph.clearEpochs();
88             for (BasicBlock* block : m_graph.blocksInNaturalOrder())
89                 handleBlock(block);
90             return true;
91         }
92             
93         case PhaseMode::Global: {
94             DFG_ASSERT(m_graph, nullptr, m_graph.m_form == SSA);
95
96             m_state = std::make_unique<InPlaceAbstractState>(m_graph);
97             m_interpreter = std::make_unique<AbstractInterpreter<InPlaceAbstractState>>(m_graph, *m_state);
98             
99             m_isConverged = false;
100             
101             // First run the analysis. Inside basic blocks we use an epoch-based analysis that
102             // is very precise. At block boundaries, we just propagate which nodes may need a
103             // barrier. This gives us a very nice bottom->top fixpoint: we start out assuming
104             // that no node needs any barriers at block boundaries, and then we converge
105             // towards believing that all nodes need barriers. "Needing a barrier" is like
106             // saying that the node is in a past epoch. "Not needing a barrier" is like saying
107             // that the node is in the current epoch.
108             m_stateAtHead = std::make_unique<BlockMap<HashSet<Node*>>>(m_graph);
109             m_stateAtTail = std::make_unique<BlockMap<HashSet<Node*>>>(m_graph);
110             
111             BlockList postOrder = m_graph.blocksInPostOrder();
112             
113             bool changed = true;
114             while (changed) {
115                 changed = false;
116                 
117                 // Intentional backwards loop because we are using RPO.
118                 for (unsigned blockIndex = postOrder.size(); blockIndex--;) {
119                     BasicBlock* block = postOrder[blockIndex];
120                     
121                     if (!handleBlock(block)) {
122                         // If the block didn't finish, then it cannot affect the fixpoint.
123                         continue;
124                     }
125                     
126                     // Construct the state-at-tail based on the epochs of live nodes and the
127                     // current epoch. We grow state-at-tail monotonically to ensure convergence.
128                     bool thisBlockChanged = false;
129                     for (Node* node : block->ssa->liveAtTail) {
130                         if (node->epoch() != m_currentEpoch) {
131                             // If the node is older than the current epoch, then we may need to
132                             // run a barrier on it in the future. So, add it to the state.
133                             thisBlockChanged |= m_stateAtTail->at(block).add(node).isNewEntry;
134                         }
135                     }
136                     
137                     if (!thisBlockChanged) {
138                         // This iteration didn't learn anything new about this block.
139                         continue;
140                     }
141                     
142                     // Changed things. Make sure that we loop one more time.
143                     changed = true;
144                     
145                     for (BasicBlock* successor : block->successors()) {
146                         for (Node* node : m_stateAtTail->at(block))
147                             m_stateAtHead->at(successor).add(node);
148                     }
149                 }
150             }
151             
152             // Tell handleBlock() that it's time to actually insert barriers for real.
153             m_isConverged = true;
154             
155             for (BasicBlock* block : m_graph.blocksInNaturalOrder())
156                 handleBlock(block);
157             
158             return true;
159         } }
160         
161         RELEASE_ASSERT_NOT_REACHED();
162         return false;
163     }
164
165 private:
166     bool handleBlock(BasicBlock* block)
167     {
168         if (verbose) {
169             dataLog("Dealing with block ", pointerDump(block), "\n");
170             if (reallyInsertBarriers())
171                 dataLog("    Really inserting barriers.\n");
172         }
173         
174         m_currentEpoch = Epoch::first();
175         
176         if (mode == PhaseMode::Global) {
177             if (!block->cfaHasVisited)
178                 return false;
179             m_state->beginBasicBlock(block);
180             
181             for (Node* node : block->ssa->liveAtHead) {
182                 if (m_stateAtHead->at(block).contains(node)) {
183                     // If previous blocks tell us that this node may need a barrier in the
184                     // future, then put it in the ancient primordial epoch. This forces us to
185                     // emit a barrier on any possibly-cell store, regardless of the epoch of the
186                     // stored value.
187                     node->setEpoch(Epoch());
188                 } else {
189                     // If previous blocks aren't requiring us to run a barrier on this node,
190                     // then put it in the current epoch. This means that we will skip barriers
191                     // on this node so long as we don't allocate. It also means that we won't
192                     // run barriers on stores to on one such node into another such node. That's
193                     // fine, because nodes would be excluded from the state set if at the tails
194                     // of all predecessors they always had the current epoch.
195                     node->setEpoch(m_currentEpoch);
196                 }
197             }
198         }
199
200         bool result = true;
201         
202         for (m_nodeIndex = 0; m_nodeIndex < block->size(); ++m_nodeIndex) {
203             m_node = block->at(m_nodeIndex);
204             
205             if (verbose) {
206                 dataLog(
207                     "    ", m_currentEpoch, ": Looking at node ", m_node, " with children: ");
208                 CommaPrinter comma;
209                 m_graph.doToChildren(
210                     m_node,
211                     [&] (Edge edge) {
212                         dataLog(comma, edge, " (", edge->epoch(), ")");
213                     });
214                 dataLog("\n");
215             }
216             
217             if (mode == PhaseMode::Global) {
218                 // Execute edges separately because we don't want to insert barriers if the
219                 // operation doing the store does a check that ensures that the child is not
220                 // a cell.
221                 m_interpreter->startExecuting();
222                 m_interpreter->executeEdges(m_node);
223             }
224             
225             switch (m_node->op()) {
226             case PutByValDirect:
227             case PutByVal:
228             case PutByValAlias: {
229                 switch (m_node->arrayMode().modeForPut().type()) {
230                 case Array::Contiguous:
231                 case Array::ArrayStorage:
232                 case Array::SlowPutArrayStorage: {
233                     Edge child1 = m_graph.varArgChild(m_node, 0);
234                     Edge child3 = m_graph.varArgChild(m_node, 2);
235                     considerBarrier(child1, child3);
236                     break;
237                 }
238                 default:
239                     break;
240                 }
241                 break;
242             }
243                 
244             case ArrayPush: {
245                 switch (m_node->arrayMode().type()) {
246                 case Array::Contiguous:
247                 case Array::ArrayStorage:
248                     considerBarrier(m_node->child1(), m_node->child2());
249                     break;
250                 default:
251                     break;
252                 }
253                 break;
254             }
255                 
256             case PutById:
257             case PutByIdFlush:
258             case PutByIdDirect:
259             case PutStructure: {
260                 considerBarrier(m_node->child1());
261                 break;
262             }
263
264             case RecordRegExpCachedResult: {
265                 considerBarrier(m_graph.varArgChild(m_node, 0));
266                 break;
267             }
268
269             case PutClosureVar:
270             case PutToArguments:
271             case SetRegExpObjectLastIndex:
272             case MultiPutByOffset: {
273                 considerBarrier(m_node->child1(), m_node->child2());
274                 break;
275             }
276                 
277             case PutByOffset: {
278                 considerBarrier(m_node->child2(), m_node->child3());
279                 break;
280             }
281                 
282             case PutGlobalVariable: {
283                 considerBarrier(m_node->child1(), m_node->child2());
284                 break;
285             }
286                 
287             case SetFunctionName: {
288                 considerBarrier(m_node->child1(), m_node->child2());
289                 break;
290             }
291
292             default:
293                 break;
294             }
295             
296             if (doesGC(m_graph, m_node))
297                 m_currentEpoch.bump();
298             
299             switch (m_node->op()) {
300             case NewObject:
301             case NewArray:
302             case NewArrayWithSize:
303             case NewArrayBuffer:
304             case NewTypedArray:
305             case NewRegexp:
306             case MaterializeNewObject:
307             case MaterializeCreateActivation:
308             case NewStringObject:
309             case MakeRope:
310             case CreateActivation:
311             case CreateDirectArguments:
312             case CreateScopedArguments:
313             case CreateClonedArguments:
314             case NewFunction:
315             case NewGeneratorFunction:
316                 // Nodes that allocate get to set their epoch because for those nodes we know
317                 // that they will be the newest object in the heap.
318                 m_node->setEpoch(m_currentEpoch);
319                 break;
320                 
321             case AllocatePropertyStorage:
322             case ReallocatePropertyStorage:
323                 // These allocate but then run their own barrier.
324                 insertBarrier(m_nodeIndex + 1, Edge(m_node->child1().node(), KnownCellUse));
325                 m_node->setEpoch(Epoch());
326                 break;
327                 
328             case Upsilon:
329                 m_node->phi()->setEpoch(m_node->epoch());
330                 m_node->setEpoch(Epoch());
331                 break;
332                 
333             default:
334                 // For nodes that aren't guaranteed to allocate, we say that their return value
335                 // (if there is one) could be arbitrarily old.
336                 m_node->setEpoch(Epoch());
337                 break;
338             }
339             
340             if (verbose) {
341                 dataLog(
342                     "    ", m_currentEpoch, ": Done with node ", m_node, " (", m_node->epoch(),
343                     ") with children: ");
344                 CommaPrinter comma;
345                 m_graph.doToChildren(
346                     m_node,
347                     [&] (Edge edge) {
348                         dataLog(comma, edge, " (", edge->epoch(), ")");
349                     });
350                 dataLog("\n");
351             }
352             
353             if (mode == PhaseMode::Global) {
354                 if (!m_interpreter->executeEffects(m_nodeIndex, m_node)) {
355                     result = false;
356                     break;
357                 }
358             }
359         }
360         
361         if (mode == PhaseMode::Global)
362             m_state->reset();
363
364         if (reallyInsertBarriers())
365             m_insertionSet.execute(block);
366         
367         return result;
368     }
369     
370     void considerBarrier(Edge base, Edge child)
371     {
372         if (verbose)
373             dataLog("        Considering adding barrier ", base, " => ", child, "\n");
374         
375         // We don't need a store barrier if the child is guaranteed to not be a cell.
376         switch (mode) {
377         case PhaseMode::Fast: {
378             // Don't try too hard because it's too expensive to run AI.
379             if (child->hasConstant()) {
380                 if (!child->asJSValue().isCell()) {
381                     if (verbose)
382                         dataLog("            Rejecting because of constant type.\n");
383                     return;
384                 }
385             } else {
386                 switch (child->result()) {
387                 case NodeResultNumber:
388                 case NodeResultDouble:
389                 case NodeResultInt32:
390                 case NodeResultInt52:
391                 case NodeResultBoolean:
392                     if (verbose)
393                         dataLog("            Rejecting because of result type.\n");
394                     return;
395                 default:
396                     break;
397                 }
398             }
399             break;
400         }
401             
402         case PhaseMode::Global: {
403             // Go into rage mode to eliminate any chance of a barrier with a non-cell child. We
404             // can afford to keep around AI in Global mode.
405             if (!m_interpreter->needsTypeCheck(child, ~SpecCell)) {
406                 if (verbose)
407                     dataLog("            Rejecting because of AI type.\n");
408                 return;
409             }
410             break;
411         } }
412         
413         considerBarrier(base);
414     }
415     
416     void considerBarrier(Edge base)
417     {
418         if (verbose)
419             dataLog("        Considering adding barrier on ", base, "\n");
420         
421         // We don't need a store barrier if the epoch of the base is identical to the current
422         // epoch. That means that we either just allocated the object and so it's guaranteed to
423         // be in newgen, or we just ran a barrier on it so it's guaranteed to be remembered
424         // already.
425         if (base->epoch() == m_currentEpoch) {
426             if (verbose)
427                 dataLog("            Rejecting because it's in the current epoch.\n");
428             return;
429         }
430         
431         if (verbose)
432             dataLog("            Inserting barrier.\n");
433         insertBarrier(m_nodeIndex, base);
434     }
435
436     void insertBarrier(unsigned nodeIndex, Edge base, bool exitOK = true)
437     {
438         // Inserting a barrier means that the object may become marked by the GC, which will make
439         // the object black.
440         base->setEpoch(Epoch());
441
442         // If we're in global mode, we should only insert the barriers once we have converged.
443         if (!reallyInsertBarriers())
444             return;
445         
446         // FIXME: We could support StoreBarrier(UntypedUse:). That would be sort of cool.
447         // But right now we don't need it.
448
449         // If the original edge was unchecked, we should also not have a check. We may be in a context
450         // where checks are not allowed. If we ever did have to insert a barrier at an ExitInvalid
451         // context and that barrier needed a check, then we could make that work by hoisting the check.
452         // That doesn't happen right now.
453         if (base.useKind() != KnownCellUse) {
454             DFG_ASSERT(m_graph, m_node, m_node->origin.exitOK);
455             base.setUseKind(CellUse);
456         }
457         
458         m_insertionSet.insertNode(
459             nodeIndex, SpecNone, StoreBarrier, m_node->origin.takeValidExit(exitOK), base);
460     }
461     
462     bool reallyInsertBarriers()
463     {
464         return mode == PhaseMode::Fast || m_isConverged;
465     }
466     
467     InsertionSet m_insertionSet;
468     Epoch m_currentEpoch;
469     unsigned m_nodeIndex;
470     Node* m_node;
471     
472     // Things we only use in Global mode.
473     std::unique_ptr<InPlaceAbstractState> m_state;
474     std::unique_ptr<AbstractInterpreter<InPlaceAbstractState>> m_interpreter;
475     std::unique_ptr<BlockMap<HashSet<Node*>>> m_stateAtHead;
476     std::unique_ptr<BlockMap<HashSet<Node*>>> m_stateAtTail;
477     bool m_isConverged;
478 };
479
480 } // anonymous namespace
481
482 bool performFastStoreBarrierInsertion(Graph& graph)
483 {
484     return runPhase<StoreBarrierInsertionPhase<PhaseMode::Fast>>(graph);
485 }
486
487 bool performGlobalStoreBarrierInsertion(Graph& graph)
488 {
489     return runPhase<StoreBarrierInsertionPhase<PhaseMode::Global>>(graph);
490 }
491
492 } } // namespace JSC::DFG
493
494 #endif // ENABLE(DFG_JIT)
495