1/*
2 * Copyright (C) 2014 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#ifndef DFGBlockWorklist_h
27#define DFGBlockWorklist_h
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGBasicBlock.h"
32#include "DFGBlockSet.h"
33#include <wtf/Vector.h>
34
35namespace JSC { namespace DFG {
36
37struct BasicBlock;
38
39class BlockWorklist {
40public:
41 BlockWorklist();
42 ~BlockWorklist();
43
44 bool push(BasicBlock*); // Returns true if we didn't know about the block before.
45
46 bool notEmpty() const { return !m_stack.isEmpty(); }
47 BasicBlock* pop();
48
49private:
50 BlockSet m_seen;
51 Vector<BasicBlock*, 16> m_stack;
52};
53
54// When you say BlockWith<int> you should read it as "block with an int".
55template<typename T>
56struct BlockWith {
57 BlockWith()
58 : block(nullptr)
59 {
60 }
61
62 BlockWith(BasicBlock* block, const T& data)
63 : block(block)
64 , data(data)
65 {
66 }
67
68 typedef void* (BlockWith<T>::*UnspecifiedBoolType);
69 operator UnspecifiedBoolType*() const
70 {
71 return block ? reinterpret_cast<UnspecifiedBoolType*>(1) : nullptr;
72 }
73
74 BasicBlock* block;
75 T data;
76};
77
78// Extended block worklist is useful for enqueueing some meta-data along with the block. It also
79// permits forcibly enqueueing things even if the block has already been seen.
80template<typename T>
81class ExtendedBlockWorklist {
82public:
83 ExtendedBlockWorklist() { }
84
85 bool forcePush(const BlockWith<T>& entry)
86 {
87 m_stack.append(entry);
88 }
89
90 bool forcePush(BasicBlock* block, const T& data)
91 {
92 forcePush(BlockWith<T>(block, data));
93 }
94
95 bool push(const BlockWith<T>& entry)
96 {
97 if (!m_seen.add(entry.block))
98 return;
99
100 forcePush(entry);
101 }
102
103 bool push(BasicBlock* block, const T& data)
104 {
105 push(BlockWith<T>(block, data));
106 }
107
108 bool notEmpty() const { return !m_stack.isEmpty(); }
109
110 BlockWith<T> pop()
111 {
112 if (m_stack.isEmpty())
113 return BlockWith<T>();
114
115 return m_stack.takeLast();
116 }
117
118private:
119 BlockSet m_seen;
120 Vector<BlockWith<T>> m_stack;
121};
122
123enum VisitOrder {
124 PreOrder,
125 PostOrder
126};
127
128struct BlockWithOrder {
129 BlockWithOrder()
130 : block(nullptr)
131 , order(PreOrder)
132 {
133 }
134
135 BlockWithOrder(BasicBlock* block, VisitOrder order)
136 : block(block)
137 , order(order)
138 {
139 }
140
141 typedef void* (BlockWithOrder::*UnspecifiedBoolType);
142 operator UnspecifiedBoolType*() const
143 {
144 return block ? reinterpret_cast<UnspecifiedBoolType*>(1) : nullptr;
145 }
146
147 BasicBlock* block;
148 VisitOrder order;
149};
150
151// Block worklist suitable for post-order traversal.
152class PostOrderBlockWorklist {
153public:
154 PostOrderBlockWorklist();
155 ~PostOrderBlockWorklist();
156
157 void pushPre(BasicBlock*);
158 void pushPost(BasicBlock*);
159
160 void push(BasicBlock* block, VisitOrder order = PreOrder)
161 {
162 switch (order) {
163 case PreOrder:
164 pushPre(block);
165 return;
166 case PostOrder:
167 pushPost(block);
168 return;
169 }
170 }
171 void push(const BlockWithOrder& data)
172 {
173 push(data.block, data.order);
174 }
175
176 bool nonEmpty() const { return !m_worklist.isEmpty(); }
177 BlockWithOrder pop();
178
179private:
180 ExtendedBlockWorklist<VisitOrder> m_worklist;
181};
182
183} } // namespace JSC::DFG
184
185#endif // ENABLE(DFG_JIT)
186
187#endif // DFGBlockWorklist_h
188