1/*
2 * Copyright (C) 2013 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
31namespace JSC { namespace DFG {
32
33class Graph;
34
35// Convert ThreadedCPS form into SSA form. This results in a form that has:
36//
37// - Roughly minimal Phi's. We use the Aycock & Horspool fixpoint for
38//   converting the CPS maximal Phis into SSA minimal Phis, with the caveat
39//   that irreducible control flow may result in some missed opportunities
40//   for Phi reduction.
41//
42// - No uses of GetLocal/SetLocal except for captured variables and flushes.
43//   After this, any remaining SetLocal means Flush. PhantomLocals become
44//   Phantoms. Nodes may have children that are in another basic block.
45//
46// - MovHints are used for OSR information, and are themselves minimal.
47//   A MovHint will occur at some point after the assigning, and at Phi
48//   points.
49//
50// - Unlike conventional SSA in which Phi functions refer to predecessors
51//   and values, our SSA uses Upsilon functions to indicate values in
52//   predecessors. A merge will look like:
53//
54//   labelA:
55//       a: Thingy(...)
56//       b: Upsilon(^e, @a)
57//       Jump(labelC)
58//
59//   labelB:
60//       c: OtherThingy(...)
61//       d: Upsilon(^e, @c)
62//       Jump(labelC)
63//
64//   labelC:
65//       e: Phi()
66//
67//   Note that the Phi has no children, but the predecessors have Upsilons
68//   that have a weak reference to the Phi (^e instead of @e; we store it
69//   in the OpInfo rather than the AdjacencyList). Think of the Upsilon
70//   as "assigning" to the "variable" associated with the Phi, and that
71//   this is the one place in SSA form where you can have multiple
72//   assignments.
73//
74//   This implies some other loosenings of SSA. For example, an Upsilon
75//   may precede a Phi in the same basic block; this may arise after CFG
76//   simplification. Although it's profitable for CFG simplification (or
77//   some other phase) to remove these, it's not strictly necessary. As
78//   well, this form allows the Upsilon to be in any block that dominates
79//   the predecessor block of the Phi, which allows for block splitting to
80//   ignore the possibility of introducing an extra edge between the Phi
81//   and the predecessor (though normal SSA would allow this, also, with
82//   the caveat that the Phi predecessor block lists would have to be
83//   updated).
84//
85//   The easiest way to convert from this SSA form into a different SSA
86//   form is to redo SSA conversion for Phi functions. That is, treat each
87//   Phi in our IR as a non-SSA variable in the foreign IR (so, as an
88//   alloca in LLVM IR, for example); the Upsilons that refer to the Phi
89//   become stores and the Phis themselves become loads.
90//
91//   Fun fact: Upsilon is so named because it comes before Phi in the
92//   alphabet. It can be written as "Y".
93
94bool performSSAConversion(Graph&);
95
96} } // namespace JSC::DFG
97
98#endif // ENABLE(DFG_JIT)
99
100#endif // DFGSSAConversionPhase_h
101
102