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