fb59770bacf1bd8a497b8128c4d9765b2fd00115
[WebKit-https.git] / Source / JavaScriptCore / b3 / air / AirLiveness.h
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. ``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 AirLiveness_h
27 #define AirLiveness_h
28
29 #if ENABLE(B3_JIT)
30
31 #include "AirBasicBlock.h"
32 #include "AirInstInlines.h"
33 #include "AirTmpInlines.h"
34 #include "B3IndexMap.h"
35 #include "B3IndexSet.h"
36 #include <wtf/IndexSparseSet.h>
37 #include <wtf/ListDump.h>
38
39 namespace JSC { namespace B3 { namespace Air {
40
41 template<Arg::Type adapterType>
42 struct TmpLivenessAdapter {
43     typedef Tmp Thing;
44     typedef HashSet<unsigned> IndexSet;
45
46     TmpLivenessAdapter(Code&) { }
47
48     static unsigned maxIndex(Code& code)
49     {
50         unsigned numTmps = code.numTmps(adapterType);
51         return AbsoluteTmpMapper<adapterType>::absoluteIndex(numTmps);
52     }
53     static bool acceptsType(Arg::Type type) { return type == adapterType; }
54     static unsigned valueToIndex(Tmp tmp) { return AbsoluteTmpMapper<adapterType>::absoluteIndex(tmp); }
55     static Tmp indexToValue(unsigned index) { return AbsoluteTmpMapper<adapterType>::tmpFromAbsoluteIndex(index); }
56 };
57
58 struct StackSlotLivenessAdapter {
59     typedef StackSlot* Thing;
60     typedef HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> IndexSet;
61
62     StackSlotLivenessAdapter(Code& code)
63         : m_code(code)
64     {
65     }
66
67     static unsigned maxIndex(Code& code)
68     {
69         return code.stackSlots().size() - 1;
70     }
71     static bool acceptsType(Arg::Type) { return true; }
72     static unsigned valueToIndex(StackSlot* stackSlot) { return stackSlot->index(); }
73     StackSlot* indexToValue(unsigned index) { return m_code.stackSlots()[index]; }
74
75 private:
76     Code& m_code;
77 };
78
79 struct RegLivenessAdapter {
80     typedef Reg Thing;
81     typedef BitVector IndexSet;
82
83     RegLivenessAdapter(Code&) { }
84
85     static unsigned maxIndex(Code&)
86     {
87         return Reg::maxIndex();
88     }
89
90     static bool acceptsType(Arg::Type) { return true; }
91     static unsigned valueToIndex(Reg reg) { return reg.index(); }
92     Reg indexToValue(unsigned index) { return Reg::fromIndex(index); }
93 };
94
95 template<typename Adapter>
96 class AbstractLiveness : private Adapter {
97     struct Workset;
98 public:
99     AbstractLiveness(Code& code)
100         : Adapter(code)
101         , m_workset(Adapter::maxIndex(code))
102         , m_liveAtHead(code.size())
103         , m_liveAtTail(code.size())
104     {
105         // The liveAtTail of each block automatically contains the LateUse's of the terminal.
106         for (BasicBlock* block : code) {
107             typename Adapter::IndexSet& liveAtTail = m_liveAtTail[block];
108
109             block->last().forEach<typename Adapter::Thing>(
110                 [&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type, Arg::Width) {
111                     if (Arg::isLateUse(role) && Adapter::acceptsType(type))
112                         liveAtTail.add(Adapter::valueToIndex(thing));
113                 });
114         }
115
116         // Blocks with new live values at tail.
117         BitVector dirtyBlocks;
118         for (size_t blockIndex = 0; blockIndex < code.size(); ++blockIndex)
119             dirtyBlocks.set(blockIndex);
120
121         bool changed;
122         do {
123             changed = false;
124
125             for (size_t blockIndex = code.size(); blockIndex--;) {
126                 BasicBlock* block = code.at(blockIndex);
127                 if (!block)
128                     continue;
129
130                 if (!dirtyBlocks.quickClear(blockIndex))
131                     continue;
132
133                 LocalCalc localCalc(*this, block);
134                 for (size_t instIndex = block->size(); instIndex--;)
135                     localCalc.execute(instIndex);
136
137                 // Handle the early def's of the first instruction.
138                 block->at(0).forEach<typename Adapter::Thing>(
139                     [&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type, Arg::Width) {
140                         if (Arg::isEarlyDef(role) && Adapter::acceptsType(type))
141                             m_workset.remove(Adapter::valueToIndex(thing));
142                     });
143
144                 Vector<unsigned>& liveAtHead = m_liveAtHead[block];
145
146                 // We only care about Tmps that were discovered in this iteration. It is impossible
147                 // to remove a live value from the head.
148                 // We remove all the values we already knew about so that we only have to deal with
149                 // what is new in LiveAtHead.
150                 if (m_workset.size() == liveAtHead.size())
151                     m_workset.clear();
152                 else {
153                     for (unsigned liveIndexAtHead : liveAtHead)
154                         m_workset.remove(liveIndexAtHead);
155                 }
156
157                 if (m_workset.isEmpty())
158                     continue;
159
160                 liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
161                 for (unsigned newValue : m_workset)
162                     liveAtHead.uncheckedAppend(newValue);
163
164                 for (BasicBlock* predecessor : block->predecessors()) {
165                     typename Adapter::IndexSet& liveAtTail = m_liveAtTail[predecessor];
166                     for (unsigned newValue : m_workset) {
167                         if (liveAtTail.add(newValue)) {
168                             if (!dirtyBlocks.quickSet(predecessor->index()))
169                                 changed = true;
170                         }
171                     }
172                 }
173             }
174         } while (changed);
175     }
176
177     // This calculator has to be run in reverse.
178     class LocalCalc {
179     public:
180         LocalCalc(AbstractLiveness& liveness, BasicBlock* block)
181             : m_liveness(liveness)
182             , m_block(block)
183         {
184             auto& workset = liveness.m_workset;
185             workset.clear();
186             typename Adapter::IndexSet& liveAtTail = liveness.m_liveAtTail[block];
187             for (unsigned index : liveAtTail)
188                 workset.add(index);
189         }
190
191         struct Iterator {
192             Iterator(Adapter& adapter, IndexSparseSet<UnsafeVectorOverflow>::const_iterator sparceSetIterator)
193                 : m_adapter(adapter)
194                 , m_sparceSetIterator(sparceSetIterator)
195             {
196             }
197
198             Iterator& operator++()
199             {
200                 ++m_sparceSetIterator;
201                 return *this;
202             }
203
204             typename Adapter::Thing operator*() const
205             {
206                 return m_adapter.indexToValue(*m_sparceSetIterator);
207             }
208
209             bool operator==(const Iterator& other) { return m_sparceSetIterator == other.m_sparceSetIterator; }
210             bool operator!=(const Iterator& other) { return m_sparceSetIterator != other.m_sparceSetIterator; }
211
212         private:
213             Adapter& m_adapter;
214             IndexSparseSet<UnsafeVectorOverflow>::const_iterator m_sparceSetIterator;
215         };
216
217         struct Iterable {
218             Iterable(AbstractLiveness& liveness)
219                 : m_liveness(liveness)
220             {
221             }
222
223             Iterator begin() const { return Iterator(m_liveness, m_liveness.m_workset.begin()); }
224             Iterator end() const { return Iterator(m_liveness, m_liveness.m_workset.end()); }
225
226         private:
227             AbstractLiveness& m_liveness;
228         };
229
230         Iterable live() const
231         {
232             return Iterable(m_liveness);
233         }
234
235         void execute(unsigned instIndex)
236         {
237             Inst& inst = m_block->at(instIndex);
238             auto& workset = m_liveness.m_workset;
239
240             // First handle the early def's of the next instruction.
241             if (instIndex + 1 < m_block->size()) {
242                 Inst& nextInst = m_block->at(instIndex + 1);
243                 nextInst.forEach<typename Adapter::Thing>(
244                     [&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type, Arg::Width) {
245                         if (Arg::isEarlyDef(role) && Adapter::acceptsType(type))
246                             workset.remove(Adapter::valueToIndex(thing));
247                     });
248             }
249             
250             // Then handle def's.
251             inst.forEach<typename Adapter::Thing>(
252                 [&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type, Arg::Width) {
253                     if (Arg::isLateDef(role) && Adapter::acceptsType(type))
254                         workset.remove(Adapter::valueToIndex(thing));
255                 });
256
257             // Then handle use's.
258             inst.forEach<typename Adapter::Thing>(
259                 [&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type, Arg::Width) {
260                     if (Arg::isEarlyUse(role) && Adapter::acceptsType(type))
261                         workset.add(Adapter::valueToIndex(thing));
262                 });
263
264             // And finally, handle the late use's of the previous instruction.
265             if (instIndex) {
266                 Inst& prevInst = m_block->at(instIndex - 1);
267                 prevInst.forEach<typename Adapter::Thing>(
268                     [&] (typename Adapter::Thing& thing, Arg::Role role, Arg::Type type, Arg::Width) {
269                         if (Arg::isLateUse(role) && Adapter::acceptsType(type))
270                             workset.add(Adapter::valueToIndex(thing));
271                     });
272             }
273         }
274
275     private:
276         AbstractLiveness& m_liveness;
277         BasicBlock* m_block;
278     };
279
280     template<typename UnderlyingIterable>
281     class Iterable {
282     public:
283         Iterable(AbstractLiveness& liveness, const UnderlyingIterable& iterable)
284             : m_liveness(liveness)
285             , m_iterable(iterable)
286         {
287         }
288
289         class iterator {
290         public:
291             iterator()
292                 : m_liveness(nullptr)
293                 , m_iter()
294             {
295             }
296             
297             iterator(AbstractLiveness& liveness, typename UnderlyingIterable::const_iterator iter)
298                 : m_liveness(&liveness)
299                 , m_iter(iter)
300             {
301             }
302
303             typename Adapter::Thing operator*()
304             {
305                 return m_liveness->indexToValue(*m_iter);
306             }
307
308             iterator& operator++()
309             {
310                 ++m_iter;
311                 return *this;
312             }
313
314             bool operator==(const iterator& other) const
315             {
316                 ASSERT(m_liveness == other.m_liveness);
317                 return m_iter == other.m_iter;
318             }
319
320             bool operator!=(const iterator& other) const
321             {
322                 return !(*this == other);
323             }
324
325         private:
326             AbstractLiveness* m_liveness;
327             typename UnderlyingIterable::const_iterator m_iter;
328         };
329
330         iterator begin() const { return iterator(m_liveness, m_iterable.begin()); }
331         iterator end() const { return iterator(m_liveness, m_iterable.end()); }
332
333     private:
334         AbstractLiveness& m_liveness;
335         const UnderlyingIterable& m_iterable;
336     };
337
338     Iterable<Vector<unsigned>> liveAtHead(BasicBlock* block)
339     {
340         return Iterable<Vector<unsigned>>(*this, m_liveAtHead[block]);
341     }
342
343     Iterable<typename Adapter::IndexSet> liveAtTail(BasicBlock* block)
344     {
345         return Iterable<typename Adapter::IndexSet>(*this, m_liveAtTail[block]);
346     }
347
348 private:
349     friend class LocalCalc;
350     friend struct LocalCalc::Iterable;
351
352     IndexSparseSet<UnsafeVectorOverflow> m_workset;
353     IndexMap<BasicBlock, Vector<unsigned>> m_liveAtHead;
354     IndexMap<BasicBlock, typename Adapter::IndexSet> m_liveAtTail;
355 };
356
357 template<Arg::Type type>
358 using TmpLiveness = AbstractLiveness<TmpLivenessAdapter<type>>;
359
360 typedef AbstractLiveness<TmpLivenessAdapter<Arg::GP>> GPLiveness;
361 typedef AbstractLiveness<TmpLivenessAdapter<Arg::FP>> FPLiveness;
362 typedef AbstractLiveness<StackSlotLivenessAdapter> StackSlotLiveness;
363 typedef AbstractLiveness<RegLivenessAdapter> RegLiveness;
364
365 } } } // namespace JSC::B3::Air
366
367 #endif // ENABLE(B3_JIT)
368
369 #endif // AirLiveness_h
370