GC constraint solving should be parallel
[WebKit-https.git] / Source / JavaScriptCore / heap / MarkingConstraintSet.h
1 /*
2  * Copyright (C) 2017 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 #pragma once
27
28 #include "MarkingConstraint.h"
29 #include <wtf/BitVector.h>
30 #include <wtf/Vector.h>
31
32 namespace JSC {
33
34 class Heap;
35 class MarkingConstraintSolver;
36
37 class MarkingConstraintSet {
38 public:
39     MarkingConstraintSet(Heap&);
40     ~MarkingConstraintSet();
41     
42     void didStartMarking();
43     
44     void add(
45         CString abbreviatedName,
46         CString name,
47         ::Function<void(SlotVisitor&)>,
48         ConstraintVolatility,
49         ConstraintConcurrency = ConstraintConcurrency::Concurrent);
50     
51     void add(std::unique_ptr<MarkingConstraint>);
52     
53     // Assuming that the mark stacks are all empty, this will give you a guess as to whether or
54     // not the wavefront is advancing.
55     bool isWavefrontAdvancing(SlotVisitor&);
56     bool isWavefrontRetreating(SlotVisitor& visitor) { return !isWavefrontAdvancing(visitor); }
57     
58     // Returns true if this executed all constraints and none of them produced new work. This
59     // assumes that you've alraedy visited roots and drained from there.
60     bool executeConvergence(SlotVisitor&);
61     
62     // Simply runs all constraints without any shenanigans.
63     void executeAll(SlotVisitor&);
64     
65 private:
66     friend class MarkingConstraintSolver;
67     
68     bool executeConvergenceImpl(SlotVisitor&);
69     
70     bool drain(SlotVisitor&, BitVector& unexecuted, BitVector& executed, bool& didVisitSomething);
71     
72     Heap& m_heap;
73     BitVector m_unexecutedRoots;
74     BitVector m_unexecutedOutgrowths;
75     Vector<std::unique_ptr<MarkingConstraint>> m_set;
76     Vector<MarkingConstraint*> m_ordered;
77     Vector<MarkingConstraint*> m_outgrowths;
78     unsigned m_iteration { 1 };
79 };
80
81 } // namespace JSC
82