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 //   The easiest way to convert from this SSA form into a different SSA
  85 //   form is to redo SSA conversion for Phi functions. That is, treat each
  86 //   Phi in our IR as a non-SSA variable in the foreign IR (so, as an
  87 //   alloca in LLVM IR, for example); the Upsilons that refer to the Phi
  88 //   become stores and the Phis themselves become loads.
  89 //
  90 //   Fun fact: Upsilon is so named because it comes before Phi in the
  91 //   alphabet. It can be written as "Y".
  92
  93 bool performSSAConversion(Graph&);
  94
  95 } } // namespace JSC::DFG
  96
  97 #endif // ENABLE(DFG_JIT)
  98
  99 #endif // DFGSSAConversionPhase_h
 100