dfg/DFGSSAConversionPhase.h

   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
  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 // - 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
  94 bool performSSAConversion(Graph&);
  95
  96 } } // namespace JSC::DFG
  97
  98 #endif // ENABLE(DFG_JIT)
  99
 100 #endif // DFGSSAConversionPhase_h
 101