1/*
2 * Copyright (C) 2011-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#pragma once
27
28#include "DFGCompilationMode.h"
29
30#if ENABLE(DFG_JIT)
31
32#include "Options.h"
33#include <limits.h>
34#include <wtf/text/StringImpl.h>
35
36namespace JSC { namespace DFG {
37
38struct Node;
39
40typedef uint32_t BlockIndex;
41static const BlockIndex NoBlock = UINT_MAX;
42
43// Use RefChildren if the child ref counts haven't already been adjusted using
44// other means and either of the following is true:
45// - The node you're creating is MustGenerate.
46// - The place where you're inserting a reference to the node you're creating
47// will not also do RefChildren.
48enum RefChildrenMode {
49 RefChildren,
50 DontRefChildren
51};
52
53// Use RefNode if you know that the node will be used from another node, and you
54// will not already be ref'ing the node to account for that use.
55enum RefNodeMode {
56 RefNode,
57 DontRefNode
58};
59
60enum SwitchKind {
61 SwitchImm,
62 SwitchChar,
63 SwitchString,
64 SwitchCell
65};
66
67inline bool verboseCompilationEnabled(CompilationMode mode = DFGMode)
68{
69 return Options::verboseCompilation() || Options::dumpGraphAtEachPhase() || (isFTL(mode) && Options::verboseFTLCompilation());
70}
71
72inline bool logCompilationChanges(CompilationMode mode = DFGMode)
73{
74 return verboseCompilationEnabled(mode) || Options::logCompilationChanges();
75}
76
77inline bool shouldDumpGraphAtEachPhase(CompilationMode mode)
78{
79 if (isFTL(mode))
80 return Options::dumpGraphAtEachPhase() || Options::dumpDFGFTLGraphAtEachPhase();
81 return Options::dumpGraphAtEachPhase() || Options::dumpDFGGraphAtEachPhase();
82}
83
84inline bool validationEnabled()
85{
86#if !ASSERT_DISABLED
87 return true;
88#else
89 return Options::validateGraph() || Options::validateGraphAtEachPhase();
90#endif
91}
92
93inline bool enableInt52()
94{
95#if USE(JSVALUE64)
96 return true;
97#else
98 return false;
99#endif
100}
101
102// The prediction propagator effectively does four passes, with the last pass
103// being done by the separate FixuPhase.
104enum PredictionPass {
105 // We're converging in a straight-forward forward flow fixpoint. This is the
106 // most conventional part of the propagator - it makes only monotonic decisions
107 // based on value profiles and rare case profiles. It ignores baseline JIT rare
108 // case profiles. The goal here is to develop a good guess of which variables
109 // are likely to be purely numerical, which generally doesn't require knowing
110 // the rare case profiles.
111 PrimaryPass,
112
113 // At this point we know what is numerical and what isn't. Non-numerical inputs
114 // to arithmetic operations will not have useful information in the Baseline JIT
115 // rare case profiles because Baseline may take slow path on non-numerical
116 // inputs even if the DFG could handle the input on the fast path. Boolean
117 // inputs are the most obvious example. This pass of prediction propagation will
118 // use Baseline rare case profiles for purely numerical operations and it will
119 // ignore them for everything else. The point of this pass is to develop a good
120 // guess of which variables are likely to be doubles.
121 //
122 // This pass is intentionally weird and goes against what is considered good
123 // form when writing a static analysis: a new data flow of booleans will cause
124 // us to ignore rare case profiles except that by then, we will have already
125 // propagated double types based on our prior assumption that we shouldn't
126 // ignore rare cases. This probably won't happen because the PrimaryPass is
127 // almost certainly going to establish what is and isn't numerical. But it's
128 // conceivable that during this pass we will discover a new boolean data flow.
129 // This ends up being sound because the prediction propagator could literally
130 // make any guesses it wants and still be sound (worst case, we OSR exit more
131 // often or use too general of types are run a bit slower). This will converge
132 // because we force monotonicity on the types of nodes and variables. So, the
133 // worst thing that can happen is that we violate basic laws of theoretical
134 // decency.
135 RareCasePass,
136
137 // At this point we know what is numerical and what isn't, and we also know what
138 // is a double and what isn't. So, we start forcing variables to be double.
139 // Doing so may have a cascading effect so this is a fixpoint. It's monotonic
140 // in the sense that once a variable is forced double, it cannot be forced in
141 // the other direction.
142 DoubleVotingPass,
143
144 // This pass occurs once we have converged. At this point we are just installing
145 // type checks based on the conclusions we have already reached. It's important
146 // for this pass to reach the same conclusions that DoubleVotingPass reached.
147 FixupPass
148};
149
150enum StructureRegistrationState { HaveNotStartedRegistering, AllStructuresAreRegistered };
151
152enum StructureRegistrationResult { StructureRegisteredNormally, StructureRegisteredAndWatched };
153
154enum OptimizationFixpointState { BeforeFixpoint, FixpointNotConverged, FixpointConverged };
155
156// Describes the form you can expect the entire graph to be in.
157enum GraphForm {
158 // LoadStore form means that basic blocks may freely use GetLocal, SetLocal,
159 // and Flush for accessing local variables and indicating where their live
160 // ranges ought to be. Data flow between local accesses is implicit. Liveness
161 // is only explicit at block heads (variablesAtHead). This is only used by
162 // the DFG simplifier and is only preserved by same.
163 //
164 // For example, LoadStore form gives no easy way to determine which SetLocal's
165 // flow into a GetLocal. As well, LoadStore form implies no restrictions on
166 // redundancy: you can freely emit multiple GetLocals, or multiple SetLocals
167 // (or any combination thereof) to the same local in the same block. LoadStore
168 // form does not require basic blocks to declare how they affect or use locals,
169 // other than implicitly by using the local ops and by preserving
170 // variablesAtHead. Finally, LoadStore allows flexibility in how liveness of
171 // locals is extended; for example you can replace a GetLocal with a Phantom
172 // and so long as the Phantom retains the GetLocal's children (i.e. the Phi
173 // most likely) then it implies that the local is still live but that it need
174 // not be stored to the stack necessarily. This implies that Phantom can
175 // reference nodes that have no result, as long as those nodes are valid
176 // GetLocal children (i.e. Phi, SetLocal, SetArgumentDefinitely, SetArgumentMaybe).
177 //
178 // LoadStore form also implies that Phis need not have children. By default,
179 // they end up having no children if you enter LoadStore using the canonical
180 // way (call Graph::dethread).
181 //
182 // LoadStore form is suitable for CFG transformations, as well as strength
183 // reduction, folding, and CSE.
184 LoadStore,
185
186 // ThreadedCPS form means that basic blocks list up-front which locals they
187 // expect to be live at the head, and which locals they make available at the
188 // tail. ThreadedCPS form also implies that:
189 //
190 // - GetLocals and SetLocals are not redundant within a basic block.
191 //
192 // - All GetLocals and Flushes are linked directly to the last access point
193 // of the variable, which must not be another GetLocal.
194 //
195 // - Phantom(Phi) is not legal, but PhantomLocal is.
196 //
197 // ThreadedCPS form is suitable for data flow analysis (CFA, prediction
198 // propagation), register allocation, and code generation.
199 ThreadedCPS,
200
201 // SSA form. See DFGSSAConversionPhase.h for a description.
202 SSA
203};
204
205// Describes the state of the UnionFind structure of VariableAccessData's.
206enum UnificationState {
207 // BasicBlock-local accesses to variables are appropriately unified with each other.
208 LocallyUnified,
209
210 // Unification has been performed globally.
211 GloballyUnified
212};
213
214// Describes how reference counts in the graph behave.
215enum RefCountState {
216 // Everything has refCount() == 1.
217 EverythingIsLive,
218
219 // Set after DCE has run.
220 ExactRefCount
221};
222
223enum OperandSpeculationMode { AutomaticOperandSpeculation, ManualOperandSpeculation };
224
225enum ProofStatus { NeedsCheck, IsProved };
226
227inline bool isProved(ProofStatus proofStatus)
228{
229 ASSERT(proofStatus == IsProved || proofStatus == NeedsCheck);
230 return proofStatus == IsProved;
231}
232
233inline ProofStatus proofStatusForIsProved(bool isProved)
234{
235 return isProved ? IsProved : NeedsCheck;
236}
237
238enum KillStatus { DoesNotKill, DoesKill };
239
240inline bool doesKill(KillStatus killStatus)
241{
242 ASSERT(killStatus == DoesNotKill || killStatus == DoesKill);
243 return killStatus == DoesKill;
244}
245
246inline KillStatus killStatusForDoesKill(bool doesKill)
247{
248 return doesKill ? DoesKill : DoesNotKill;
249}
250
251enum class PlanStage {
252 Initial,
253 AfterFixup
254};
255
256// If possible, this will acquire a lock to make sure that if multiple threads
257// start crashing at the same time, you get coherent dump output. Use this only
258// when you're forcing a crash with diagnostics.
259void startCrashing();
260
261JS_EXPORT_PRIVATE bool isCrashing();
262
263struct NodeAndIndex {
264 NodeAndIndex()
265 : node(nullptr)
266 , index(UINT_MAX)
267 {
268 }
269
270 NodeAndIndex(Node* node, unsigned index)
271 : node(node)
272 , index(index)
273 {
274 ASSERT(!node == (index == UINT_MAX));
275 }
276
277 bool operator!() const
278 {
279 return !node;
280 }
281
282 Node* node;
283 unsigned index;
284};
285
286// A less-than operator for strings that is useful for generating string switches. Sorts by <
287// relation on characters. Ensures that if a is a prefix of b, then a < b.
288bool stringLessThan(StringImpl& a, StringImpl& b);
289
290} } // namespace JSC::DFG
291
292namespace WTF {
293
294void printInternal(PrintStream&, JSC::DFG::OptimizationFixpointState);
295void printInternal(PrintStream&, JSC::DFG::GraphForm);
296void printInternal(PrintStream&, JSC::DFG::UnificationState);
297void printInternal(PrintStream&, JSC::DFG::RefCountState);
298void printInternal(PrintStream&, JSC::DFG::ProofStatus);
299
300} // namespace WTF
301
302#endif // ENABLE(DFG_JIT)
303
304namespace JSC { namespace DFG {
305
306// Put things here that must be defined even if ENABLE(DFG_JIT) is false.
307
308enum CapabilityLevel {
309 CannotCompile,
310 CanCompile,
311 CanCompileAndInline,
312 CapabilityLevelNotSet
313};
314
315inline bool canCompile(CapabilityLevel level)
316{
317 switch (level) {
318 case CanCompile:
319 case CanCompileAndInline:
320 return true;
321 default:
322 return false;
323 }
324}
325
326inline bool canInline(CapabilityLevel level)
327{
328 switch (level) {
329 case CanCompileAndInline:
330 return true;
331 default:
332 return false;
333 }
334}
335
336inline CapabilityLevel leastUpperBound(CapabilityLevel a, CapabilityLevel b)
337{
338 switch (a) {
339 case CannotCompile:
340 return CannotCompile;
341 case CanCompile:
342 switch (b) {
343 case CanCompile:
344 case CanCompileAndInline:
345 return CanCompile;
346 default:
347 return CannotCompile;
348 }
349 case CanCompileAndInline:
350 return b;
351 case CapabilityLevelNotSet:
352 ASSERT_NOT_REACHED();
353 return CannotCompile;
354 }
355 ASSERT_NOT_REACHED();
356 return CannotCompile;
357}
358
359// Unconditionally disable DFG disassembly support if the DFG is not compiled in.
360inline bool shouldDumpDisassembly(CompilationMode mode = DFGMode)
361{
362#if ENABLE(DFG_JIT)
363 return Options::dumpDisassembly() || Options::dumpDFGDisassembly() || (isFTL(mode) && Options::dumpFTLDisassembly());
364#else
365 UNUSED_PARAM(mode);
366 return false;
367#endif
368}
369
370} } // namespace JSC::DFG
371
372namespace WTF {
373
374void printInternal(PrintStream&, JSC::DFG::CapabilityLevel);
375
376} // namespace WTF
377