Remove remaining references to LLVM, and make sure comments refer to the backend...
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGSSAConversionPhase.h
1 /*
2  * Copyright (C) 2013, 2014 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 DFGSSAConversionPhase_h
27 #define DFGSSAConversionPhase_h
28
29 #if ENABLE(DFG_JIT)
30
31 namespace JSC { namespace DFG {
32
33 class Graph;
34
35 // Convert ThreadedCPS form into SSA form. This results in a form that has:
36 //
37 // - Minimal Phi's. We use the the Cytron et al (TOPLAS'91) algorithm for
38 //   Phi insertion. Most of the algorithm is implemented in SSACalculator
39 //   and Dominators.
40 //
41 // - No uses of GetLocal/SetLocal except for captured variables and flushes.
42 //   After this, any remaining SetLocal means Flush. PhantomLocals become
43 //   Phantoms. Nodes may have children that are in another basic block.
44 //
45 // - MovHints are used for OSR information, and are themselves minimal.
46 //   A MovHint will occur at some point after the assigning, and at Phi
47 //   points.
48 //
49 // - Unlike conventional SSA in which Phi functions refer to predecessors
50 //   and values, our SSA uses Upsilon functions to indicate values in
51 //   predecessors. A merge will look like:
52 //
53 //   labelA:
54 //       a: Thingy(...)
55 //       b: Upsilon(^e, @a)
56 //       Jump(labelC)
57 //
58 //   labelB:
59 //       c: OtherThingy(...)
60 //       d: Upsilon(^e, @c)
61 //       Jump(labelC)
62 //
63 //   labelC:
64 //       e: Phi()
65 //
66 //   Note that the Phi has no children, but the predecessors have Upsilons
67 //   that have a weak reference to the Phi (^e instead of @e; we store it
68 //   in the OpInfo rather than the AdjacencyList). Think of the Upsilon
69 //   as "assigning" to the "variable" associated with the Phi, and that
70 //   this is the one place in SSA form where you can have multiple
71 //   assignments.
72 //
73 //   This implies some other loosenings of SSA. For example, an Upsilon
74 //   may precede a Phi in the same basic block; this may arise after CFG
75 //   simplification. Although it's profitable for CFG simplification (or
76 //   some other phase) to remove these, it's not strictly necessary. As
77 //   well, this form allows the Upsilon to be in any block that dominates
78 //   the predecessor block of the Phi, which allows for block splitting to
79 //   ignore the possibility of introducing an extra edge between the Phi
80 //   and the predecessor (though normal SSA would allow this, also, with
81 //   the caveat that the Phi predecessor block lists would have to be
82 //   updated).
83 //
84 //   Fun fact: Upsilon is so named because it comes before Phi in the
85 //   alphabet. It can be written as "Y".
86
87 bool performSSAConversion(Graph&);
88
89 } } // namespace JSC::DFG
90
91 #endif // ENABLE(DFG_JIT)
92
93 #endif // DFGSSAConversionPhase_h
94