B3 CSE should be able to match a full redundancy even if none of the matches dominate...
[WebKit-https.git] / Source / JavaScriptCore / b3 / B3Procedure.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 B3Procedure_h
27 #define B3Procedure_h
28
29 #if ENABLE(B3_JIT)
30
31 #include "B3OpaqueByproducts.h"
32 #include "B3Origin.h"
33 #include "B3Type.h"
34 #include "B3ValueKey.h"
35 #include "PureNaN.h"
36 #include "RegisterAtOffsetList.h"
37 #include <wtf/Bag.h>
38 #include <wtf/FastMalloc.h>
39 #include <wtf/HashSet.h>
40 #include <wtf/Noncopyable.h>
41 #include <wtf/PrintStream.h>
42 #include <wtf/SharedTask.h>
43 #include <wtf/TriState.h>
44 #include <wtf/Vector.h>
45
46 namespace JSC { namespace B3 {
47
48 class BasicBlock;
49 class BlockInsertionSet;
50 class CFG;
51 class Dominators;
52 class Value;
53
54 namespace Air { class Code; }
55
56 class Procedure {
57     WTF_MAKE_NONCOPYABLE(Procedure);
58     WTF_MAKE_FAST_ALLOCATED;
59 public:
60
61     JS_EXPORT_PRIVATE Procedure();
62     JS_EXPORT_PRIVATE ~Procedure();
63
64     template<typename Callback>
65     void setOriginPrinter(Callback&& callback)
66     {
67         m_originPrinter = createSharedTask<void(PrintStream&, Origin)>(
68             std::forward<Callback>(callback));
69     }
70
71     // Usually you use this via OriginDump, though it's cool to use it directly.
72     void printOrigin(PrintStream& out, Origin origin) const;
73
74     // This is a debugging hack. Sometimes while debugging B3 you need to break the abstraction
75     // and get at the DFG Graph, or whatever data structure the frontend used to describe the
76     // program. The FTL passes the DFG Graph.
77     void setFrontendData(const void* value) { m_frontendData = value; }
78     const void* frontendData() const { return m_frontendData; }
79
80     JS_EXPORT_PRIVATE BasicBlock* addBlock(double frequency = 1);
81     
82     template<typename ValueType, typename... Arguments>
83     ValueType* add(Arguments...);
84
85     Value* clone(Value*);
86
87     Value* addIntConstant(Origin, Type, int64_t value);
88     Value* addIntConstant(Value*, int64_t value);
89
90     Value* addBottom(Origin, Type);
91     Value* addBottom(Value*);
92
93     // Returns null for MixedTriState.
94     Value* addBoolConstant(Origin, TriState);
95
96     void resetValueOwners();
97     void resetReachability();
98
99     // This destroys CFG analyses. If we ask for them again, we will recompute them. Usually you
100     // should call this anytime you call resetReachability().
101     void invalidateCFG();
102
103     JS_EXPORT_PRIVATE void dump(PrintStream&) const;
104
105     unsigned size() const { return m_blocks.size(); }
106     BasicBlock* at(unsigned index) const { return m_blocks[index].get(); }
107     BasicBlock* operator[](unsigned index) const { return at(index); }
108
109     class iterator {
110     public:
111         iterator()
112             : m_procedure(nullptr)
113             , m_index(0)
114         {
115         }
116
117         iterator(const Procedure& procedure, unsigned index)
118             : m_procedure(&procedure)
119             , m_index(findNext(index))
120         {
121         }
122
123         BasicBlock* operator*()
124         {
125             return m_procedure->at(m_index);
126         }
127
128         iterator& operator++()
129         {
130             m_index = findNext(m_index + 1);
131             return *this;
132         }
133
134         bool operator==(const iterator& other) const
135         {
136             ASSERT(m_procedure == other.m_procedure);
137             return m_index == other.m_index;
138         }
139         
140         bool operator!=(const iterator& other) const
141         {
142             return !(*this == other);
143         }
144
145     private:
146         unsigned findNext(unsigned index)
147         {
148             while (index < m_procedure->size() && !m_procedure->at(index))
149                 index++;
150             return index;
151         }
152
153         const Procedure* m_procedure;
154         unsigned m_index;
155     };
156
157     iterator begin() const { return iterator(*this, 0); }
158     iterator end() const { return iterator(*this, size()); }
159
160     Vector<BasicBlock*> blocksInPreOrder();
161     Vector<BasicBlock*> blocksInPostOrder();
162
163     class ValuesCollection {
164     public:
165         ValuesCollection(const Procedure& procedure)
166             : m_procedure(procedure)
167         {
168         }
169
170         class iterator {
171         public:
172             iterator()
173                 : m_procedure(nullptr)
174                 , m_index(0)
175             {
176             }
177
178             iterator(const Procedure& procedure, unsigned index)
179                 : m_procedure(&procedure)
180                 , m_index(findNext(index))
181             {
182             }
183
184             Value* operator*() const
185             {
186                 return m_procedure->m_values[m_index].get();
187             }
188
189             iterator& operator++()
190             {
191                 m_index = findNext(m_index + 1);
192                 return *this;
193             }
194
195             bool operator==(const iterator& other) const
196             {
197                 ASSERT(m_procedure == other.m_procedure);
198                 return m_index == other.m_index;
199             }
200
201             bool operator!=(const iterator& other) const
202             {
203                 return !(*this == other);
204             }
205
206         private:
207             unsigned findNext(unsigned index)
208             {
209                 while (index < m_procedure->m_values.size() && !m_procedure->m_values[index])
210                     index++;
211                 return index;
212             }
213
214             const Procedure* m_procedure;
215             unsigned m_index;
216         };
217
218         iterator begin() const { return iterator(m_procedure, 0); }
219         iterator end() const { return iterator(m_procedure, m_procedure.m_values.size()); }
220
221         unsigned size() const { return m_procedure.m_values.size(); }
222         Value* at(unsigned index) const { return m_procedure.m_values[index].get(); }
223         Value* operator[](unsigned index) const { return at(index); }
224         
225     private:
226         const Procedure& m_procedure;
227     };
228
229     ValuesCollection values() const { return ValuesCollection(*this); }
230
231     void deleteValue(Value*);
232
233     // A valid procedure cannot contain any orphan values. An orphan is a value that is not in
234     // any basic block. It is possible to create an orphan value during code generation or during
235     // transformation. If you know that you may have created some, you can call this method to
236     // delete them, making the procedure valid again.
237     void deleteOrphans();
238
239     CFG& cfg() const { return *m_cfg; }
240
241     Dominators& dominators();
242
243     void addFastConstant(const ValueKey&);
244     bool isFastConstant(const ValueKey&);
245
246     // The name has to be a string literal, since we don't do any memory management for the string.
247     void setLastPhaseName(const char* name)
248     {
249         m_lastPhaseName = name;
250     }
251
252     const char* lastPhaseName() const { return m_lastPhaseName; }
253
254     void* addDataSection(size_t size);
255
256     OpaqueByproducts& byproducts() { return *m_byproducts; }
257
258     // Below are methods that make sense to call after you have generated code for the procedure.
259
260     // You have to call this method after calling generate(). The code generated by B3::generate()
261     // will require you to keep this object alive for as long as that code is runnable. Usually, this
262     // just keeps alive things like the double constant pool and switch lookup tables. If this sounds
263     // confusing, you should probably be using the B3::Compilation API to compile code. If you use
264     // that API, then you don't have to worry about this.
265     std::unique_ptr<OpaqueByproducts> releaseByproducts() { return WTFMove(m_byproducts); }
266
267     // This gives you direct access to Code. However, the idea is that clients of B3 shouldn't have to
268     // call this. So, Procedure has some methods (below) that expose some Air::Code functionality.
269     const Air::Code& code() const { return *m_code; }
270     Air::Code& code() { return *m_code; }
271
272     unsigned callArgAreaSize() const;
273     void requestCallArgAreaSize(unsigned size);
274
275     JS_EXPORT_PRIVATE unsigned frameSize() const;
276     const RegisterAtOffsetList& calleeSaveRegisters() const;
277
278 private:
279     friend class BlockInsertionSet;
280     
281     JS_EXPORT_PRIVATE size_t addValueIndex();
282     
283     Vector<std::unique_ptr<BasicBlock>> m_blocks;
284     Vector<std::unique_ptr<Value>> m_values;
285     Vector<size_t> m_valueIndexFreeList;
286     std::unique_ptr<CFG> m_cfg;
287     std::unique_ptr<Dominators> m_dominators;
288     HashSet<ValueKey> m_fastConstants;
289     const char* m_lastPhaseName;
290     std::unique_ptr<OpaqueByproducts> m_byproducts;
291     std::unique_ptr<Air::Code> m_code;
292     RefPtr<SharedTask<void(PrintStream&, Origin)>> m_originPrinter;
293     const void* m_frontendData;
294 };
295
296 } } // namespace JSC::B3
297
298 #endif // ENABLE(B3_JIT)
299
300 #endif // B3Procedure_h
301