blob: 469df3f3150a7e2930a4bd399b779a64d0aefa08 [file] [log] [blame]
fpizlo@apple.comcbac0922017-03-27 04:17:52 +00001/*
2 * Copyright (C) 2015-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. ``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#pragma once
27
28#include <wtf/BitVector.h>
29#include <wtf/IndexSparseSet.h>
fpizlo@apple.comcbac0922017-03-27 04:17:52 +000030#include <wtf/StdLibExtras.h>
31
32namespace WTF {
33
34// HEADS UP: The algorithm here is duplicated in AirRegLiveness.h. That one uses sets rather
35// than fancy vectors, because that's better for register liveness analysis.
36template<typename Adapter>
37class Liveness : public Adapter {
38public:
39 typedef typename Adapter::CFG CFG;
40 typedef typename Adapter::Thing Thing;
41 typedef Vector<unsigned, 4, UnsafeVectorOverflow> IndexVector;
fpizlo@apple.com1503e102017-04-05 00:25:02 +000042 typedef IndexSparseSet<unsigned, DefaultIndexSparseSetTraits<unsigned>, UnsafeVectorOverflow> Workset;
fpizlo@apple.comcbac0922017-03-27 04:17:52 +000043
44 template<typename... Arguments>
45 Liveness(CFG& cfg, Arguments&&... arguments)
46 : Adapter(std::forward<Arguments>(arguments)...)
47 , m_cfg(cfg)
48 , m_workset(Adapter::numIndices())
49 , m_liveAtHead(cfg.template newMap<IndexVector>())
50 , m_liveAtTail(cfg.template newMap<IndexVector>())
51 {
fpizlo@apple.comcbac0922017-03-27 04:17:52 +000052 }
fpizlo@apple.com53f67622017-04-04 19:09:03 +000053
fpizlo@apple.comcbac0922017-03-27 04:17:52 +000054 // This calculator has to be run in reverse.
55 class LocalCalc {
ysuzuki@apple.com2a31ffc2019-08-12 20:57:15 +000056 WTF_MAKE_FAST_ALLOCATED;
fpizlo@apple.comcbac0922017-03-27 04:17:52 +000057 public:
58 LocalCalc(Liveness& liveness, typename CFG::Node block)
59 : m_liveness(liveness)
60 , m_block(block)
61 {
62 auto& workset = liveness.m_workset;
63 workset.clear();
64 IndexVector& liveAtTail = liveness.m_liveAtTail[block];
65 for (unsigned index : liveAtTail)
66 workset.add(index);
67 }
68
69 class Iterable {
ysuzuki@apple.com2a31ffc2019-08-12 20:57:15 +000070 WTF_MAKE_FAST_ALLOCATED;
fpizlo@apple.comcbac0922017-03-27 04:17:52 +000071 public:
72 Iterable(Liveness& liveness)
73 : m_liveness(liveness)
74 {
75 }
76
77 class iterator {
ysuzuki@apple.com2a31ffc2019-08-12 20:57:15 +000078 WTF_MAKE_FAST_ALLOCATED;
fpizlo@apple.comcbac0922017-03-27 04:17:52 +000079 public:
fpizlo@apple.com1503e102017-04-05 00:25:02 +000080 iterator(Adapter& adapter, Workset::const_iterator sparceSetIterator)
fpizlo@apple.comcbac0922017-03-27 04:17:52 +000081 : m_adapter(adapter)
82 , m_sparceSetIterator(sparceSetIterator)
83 {
84 }
85
86 iterator& operator++()
87 {
88 ++m_sparceSetIterator;
89 return *this;
90 }
91
92 typename Adapter::Thing operator*() const
93 {
94 return m_adapter.indexToValue(*m_sparceSetIterator);
95 }
96
97 bool operator==(const iterator& other) { return m_sparceSetIterator == other.m_sparceSetIterator; }
98 bool operator!=(const iterator& other) { return m_sparceSetIterator != other.m_sparceSetIterator; }
99
100 private:
101 Adapter& m_adapter;
fpizlo@apple.com1503e102017-04-05 00:25:02 +0000102 Workset::const_iterator m_sparceSetIterator;
fpizlo@apple.comcbac0922017-03-27 04:17:52 +0000103 };
104
105 iterator begin() const { return iterator(m_liveness, m_liveness.m_workset.begin()); }
106 iterator end() const { return iterator(m_liveness, m_liveness.m_workset.end()); }
107
108 bool contains(const typename Adapter::Thing& thing) const
109 {
fpizlo@apple.com0bfdeef2017-04-07 00:11:16 +0000110 return m_liveness.m_workset.contains(m_liveness.valueToIndex(thing));
fpizlo@apple.comcbac0922017-03-27 04:17:52 +0000111 }
112
113 private:
114 Liveness& m_liveness;
115 };
116
117 Iterable live() const
118 {
119 return Iterable(m_liveness);
120 }
121
122 bool isLive(const typename Adapter::Thing& thing) const
123 {
124 return live().contains(thing);
125 }
126
127 void execute(unsigned instIndex)
128 {
129 auto& workset = m_liveness.m_workset;
130
fpizlo@apple.comcb79e092017-04-03 20:50:33 +0000131 // Want an easy example to help you visualize how this works?
132 // Check out B3VariableLiveness.h.
133 //
134 // Want a hard example to help you understand the hard cases?
135 // Check out AirLiveness.h.
136
137 m_liveness.forEachDef(
fpizlo@apple.comcbac0922017-03-27 04:17:52 +0000138 m_block, instIndex + 1,
139 [&] (unsigned index) {
140 workset.remove(index);
141 });
142
fpizlo@apple.comcb79e092017-04-03 20:50:33 +0000143 m_liveness.forEachUse(
fpizlo@apple.comcbac0922017-03-27 04:17:52 +0000144 m_block, instIndex,
145 [&] (unsigned index) {
fpizlo@apple.comcbac0922017-03-27 04:17:52 +0000146 workset.add(index);
147 });
148 }
149
150 private:
151 Liveness& m_liveness;
152 typename CFG::Node m_block;
153 };
154
155 const IndexVector& rawLiveAtHead(typename CFG::Node block)
156 {
157 return m_liveAtHead[block];
158 }
159
160 template<typename UnderlyingIterable>
161 class Iterable {
ysuzuki@apple.com2a31ffc2019-08-12 20:57:15 +0000162 WTF_MAKE_FAST_ALLOCATED;
fpizlo@apple.comcbac0922017-03-27 04:17:52 +0000163 public:
164 Iterable(Liveness& liveness, const UnderlyingIterable& iterable)
165 : m_liveness(liveness)
166 , m_iterable(iterable)
167 {
168 }
169
170 class iterator {
ysuzuki@apple.com2a31ffc2019-08-12 20:57:15 +0000171 WTF_MAKE_FAST_ALLOCATED;
fpizlo@apple.comcbac0922017-03-27 04:17:52 +0000172 public:
173 iterator()
174 : m_liveness(nullptr)
175 , m_iter()
176 {
177 }
178
179 iterator(Liveness& liveness, typename UnderlyingIterable::const_iterator iter)
180 : m_liveness(&liveness)
181 , m_iter(iter)
182 {
183 }
184
185 typename Adapter::Thing operator*()
186 {
187 return m_liveness->indexToValue(*m_iter);
188 }
189
190 iterator& operator++()
191 {
192 ++m_iter;
193 return *this;
194 }
195
196 bool operator==(const iterator& other) const
197 {
198 ASSERT(m_liveness == other.m_liveness);
199 return m_iter == other.m_iter;
200 }
201
202 bool operator!=(const iterator& other) const
203 {
204 return !(*this == other);
205 }
206
207 private:
208 Liveness* m_liveness;
209 typename UnderlyingIterable::const_iterator m_iter;
210 };
211
212 iterator begin() const { return iterator(m_liveness, m_iterable.begin()); }
213 iterator end() const { return iterator(m_liveness, m_iterable.end()); }
214
215 bool contains(const typename Adapter::Thing& thing) const
216 {
fpizlo@apple.com0bfdeef2017-04-07 00:11:16 +0000217 return m_liveness.m_workset.contains(m_liveness.valueToIndex(thing));
fpizlo@apple.comcbac0922017-03-27 04:17:52 +0000218 }
219
220 private:
221 Liveness& m_liveness;
222 const UnderlyingIterable& m_iterable;
223 };
224
225 Iterable<IndexVector> liveAtHead(typename CFG::Node block)
226 {
227 return Iterable<IndexVector>(*this, m_liveAtHead[block]);
228 }
229
230 Iterable<IndexVector> liveAtTail(typename CFG::Node block)
231 {
232 return Iterable<IndexVector>(*this, m_liveAtTail[block]);
233 }
234
fpizlo@apple.com1503e102017-04-05 00:25:02 +0000235 Workset& workset() { return m_workset; }
fpizlo@apple.comcbac0922017-03-27 04:17:52 +0000236
237 class LiveAtHead {
ysuzuki@apple.com2a31ffc2019-08-12 20:57:15 +0000238 WTF_MAKE_FAST_ALLOCATED;
fpizlo@apple.comcbac0922017-03-27 04:17:52 +0000239 public:
240 LiveAtHead(Liveness& liveness)
241 : m_liveness(liveness)
242 {
243 for (unsigned blockIndex = m_liveness.m_cfg.numNodes(); blockIndex--;) {
244 typename CFG::Node block = m_liveness.m_cfg.node(blockIndex);
245 if (!block)
246 continue;
247
248 std::sort(m_liveness.m_liveAtHead[block].begin(), m_liveness.m_liveAtHead[block].end());
249 }
250 }
251
252 bool isLiveAtHead(typename CFG::Node block, const typename Adapter::Thing& thing)
253 {
254 return !!tryBinarySearch<unsigned>(m_liveness.m_liveAtHead[block], m_liveness.m_liveAtHead[block].size(), m_liveness.valueToIndex(thing), [] (unsigned* value) { return *value; });
255 }
256
257 private:
258 Liveness& m_liveness;
259 };
260
261 LiveAtHead liveAtHead() { return LiveAtHead(*this); }
262
fpizlo@apple.com53f67622017-04-04 19:09:03 +0000263protected:
264 void compute()
265 {
fpizlo@apple.com0bfdeef2017-04-07 00:11:16 +0000266 Adapter::prepareToCompute();
267
fpizlo@apple.com53f67622017-04-04 19:09:03 +0000268 // The liveAtTail of each block automatically contains the LateUse's of the terminal.
269 for (unsigned blockIndex = m_cfg.numNodes(); blockIndex--;) {
270 typename CFG::Node block = m_cfg.node(blockIndex);
271 if (!block)
272 continue;
273
274 IndexVector& liveAtTail = m_liveAtTail[block];
275
276 Adapter::forEachUse(
277 block, Adapter::blockSize(block),
278 [&] (unsigned index) {
279 liveAtTail.append(index);
280 });
281
282 std::sort(liveAtTail.begin(), liveAtTail.end());
283 removeRepeatedElements(liveAtTail);
284 }
285
286 // Blocks with new live values at tail.
287 BitVector dirtyBlocks;
288 for (size_t blockIndex = m_cfg.numNodes(); blockIndex--;)
289 dirtyBlocks.set(blockIndex);
290
291 IndexVector mergeBuffer;
292
293 bool changed;
294 do {
295 changed = false;
296
297 for (size_t blockIndex = m_cfg.numNodes(); blockIndex--;) {
298 typename CFG::Node block = m_cfg.node(blockIndex);
299 if (!block)
300 continue;
301
302 if (!dirtyBlocks.quickClear(blockIndex))
303 continue;
304
305 LocalCalc localCalc(*this, block);
306 for (size_t instIndex = Adapter::blockSize(block); instIndex--;)
307 localCalc.execute(instIndex);
308
309 // Handle the early def's of the first instruction.
310 Adapter::forEachDef(
311 block, 0,
312 [&] (unsigned index) {
313 m_workset.remove(index);
314 });
315
316 IndexVector& liveAtHead = m_liveAtHead[block];
317
318 // We only care about Tmps that were discovered in this iteration. It is impossible
319 // to remove a live value from the head.
320 // We remove all the values we already knew about so that we only have to deal with
321 // what is new in LiveAtHead.
322 if (m_workset.size() == liveAtHead.size())
323 m_workset.clear();
324 else {
325 for (unsigned liveIndexAtHead : liveAtHead)
326 m_workset.remove(liveIndexAtHead);
327 }
328
329 if (m_workset.isEmpty())
330 continue;
331
332 liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
333 for (unsigned newValue : m_workset)
334 liveAtHead.uncheckedAppend(newValue);
335
336 m_workset.sort();
337
338 for (typename CFG::Node predecessor : m_cfg.predecessors(block)) {
339 IndexVector& liveAtTail = m_liveAtTail[predecessor];
340
341 if (liveAtTail.isEmpty())
342 liveAtTail = m_workset.values();
343 else {
344 mergeBuffer.resize(liveAtTail.size() + m_workset.size());
345 auto iter = mergeDeduplicatedSorted(
346 liveAtTail.begin(), liveAtTail.end(),
347 m_workset.begin(), m_workset.end(),
348 mergeBuffer.begin());
349 mergeBuffer.resize(iter - mergeBuffer.begin());
350
351 if (mergeBuffer.size() == liveAtTail.size())
352 continue;
353
354 RELEASE_ASSERT(mergeBuffer.size() > liveAtTail.size());
355 liveAtTail = mergeBuffer;
356 }
357
358 dirtyBlocks.quickSet(predecessor->index());
359 changed = true;
360 }
361 }
362 } while (changed);
363 }
364
fpizlo@apple.comcbac0922017-03-27 04:17:52 +0000365private:
366 friend class LocalCalc;
367 friend class LocalCalc::Iterable;
368
369 CFG& m_cfg;
fpizlo@apple.com1503e102017-04-05 00:25:02 +0000370 Workset m_workset;
fpizlo@apple.comcbac0922017-03-27 04:17:52 +0000371 typename CFG::template Map<IndexVector> m_liveAtHead;
372 typename CFG::template Map<IndexVector> m_liveAtTail;
373};
374
375} // namespace WTF
376