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