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