dfg/DFGCommon.h

   1 /*
   2  * Copyright (C) 2011-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 DFGCommon_h
  27 #define DFGCommon_h
  28
  29 #include "DFGCompilationMode.h"
  30
  31 #if ENABLE(DFG_JIT)
  32
  33 #include "CodeOrigin.h"
  34 #include "Options.h"
  35 #include "VirtualRegister.h"
  36
  37 namespace JSC { namespace DFG {
  38
  39 struct Node;
  40
  41 typedef uint32_t BlockIndex;
  42 static const BlockIndex NoBlock = UINT_MAX;
  43
  44 struct NodePointerTraits {
  45     static Node* defaultValue() { return 0; }
  46     static bool isEmptyForDump(Node* value) { return !value; }
  47 };
  48
  49 // Use RefChildren if the child ref counts haven't already been adjusted using
  50 // other means and either of the following is true:
  51 // - The node you're creating is MustGenerate.
  52 // - The place where you're inserting a reference to the node you're creating
  53 //   will not also do RefChildren.
  54 enum RefChildrenMode {
  55     RefChildren,
  56     DontRefChildren
  57 };
  58
  59 // Use RefNode if you know that the node will be used from another node, and you
  60 // will not already be ref'ing the node to account for that use.
  61 enum RefNodeMode {
  62     RefNode,
  63     DontRefNode
  64 };
  65
  66 inline bool verboseCompilationEnabled(CompilationMode mode = DFGMode)
  67 {
  68     return Options::verboseCompilation() || Options::dumpGraphAtEachPhase() || (isFTL(mode) && Options::verboseFTLCompilation());
  69 }
  70
  71 inline bool logCompilationChanges(CompilationMode mode = DFGMode)
  72 {
  73     return verboseCompilationEnabled(mode) || Options::logCompilationChanges();
  74 }
  75
  76 inline bool shouldDumpGraphAtEachPhase()
  77 {
  78     return Options::dumpGraphAtEachPhase();
  79 }
  80
  81 inline bool validationEnabled()
  82 {
  83 #if !ASSERT_DISABLED
  84     return true;
  85 #else
  86     return Options::validateGraph() || Options::validateGraphAtEachPhase();
  87 #endif
  88 }
  89
  90 inline bool enableInt52()
  91 {
  92 #if USE(JSVALUE64)
  93     return true;
  94 #else
  95     return false;
  96 #endif
  97 }
  98
  99 enum NoResultTag { NoResult };
 100
 101 // The prediction propagator effectively does four passes, with the last pass
 102 // being done by the separate FixuPhase.
 103 enum PredictionPass {
 104     // We're converging in a straght-forward forward flow fixpoint. This is the
 105     // most conventional part of the propagator - it makes only monotonic decisions
 106     // based on value profiles and rare case profiles. It ignores baseline JIT rare
 107     // case profiles. The goal here is to develop a good guess of which variables
 108     // are likely to be purely numerical, which generally doesn't require knowing
 109     // the rare case profiles.
 110     PrimaryPass,
 111
 112     // At this point we know what is numerical and what isn't. Non-numerical inputs
 113     // to arithmetic operations will not have useful information in the Baseline JIT
 114     // rare case profiles because Baseline may take slow path on non-numerical
 115     // inputs even if the DFG could handle the input on the fast path. Boolean
 116     // inputs are the most obvious example. This pass of prediction propagation will
 117     // use Baseline rare case profiles for purely numerical operations and it will
 118     // ignore them for everything else. The point of this pass is to develop a good
 119     // guess of which variables are likely to be doubles.
 120     //
 121     // This pass is intentionally weird and goes against what is considered good
 122     // form when writing a static analysis: a new data flow of booleans will cause
 123     // us to ignore rare case profiles except that by then, we will have already
 124     // propagated double types based on our prior assumption that we shouldn't
 125     // ignore rare cases. This probably won't happen because the PrimaryPass is
 126     // almost certainly going to establish what is and isn't numerical. But it's
 127     // conceivable that during this pass we will discover a new boolean data flow.
 128     // This ends up being sound because the prediction propagator could literally
 129     // make any guesses it wants and still be sound (worst case, we OSR exit more
 130     // often or use too general of types are run a bit slower). This will converge
 131     // because we force monotonicity on the types of nodes and variables. So, the
 132     // worst thing that can happen is that we violate basic laws of theoretical
 133     // decency.
 134     RareCasePass,
 135
 136     // At this point we know what is numerical and what isn't, and we also know what
 137     // is a double and what isn't. So, we start forcing variables to be double.
 138     // Doing so may have a cascading effect so this is a fixpoint. It's monotonic
 139     // in the sense that once a variable is forced double, it cannot be forced in
 140     // the other direction.
 141     DoubleVotingPass,
 142
 143     // This pass occurs once we have converged. At this point we are just installing
 144     // type checks based on the conclusions we have already reached. It's important
 145     // for this pass to reach the same conclusions that DoubleVotingPass reached.
 146     FixupPass
 147 };
 148
 149 enum OptimizationFixpointState { BeforeFixpoint, FixpointNotConverged, FixpointConverged };
 150
 151 // Describes the form you can expect the entire graph to be in.
 152 enum GraphForm {
 153     // LoadStore form means that basic blocks may freely use GetLocal, SetLocal,
 154     // GetLocalUnlinked, and Flush for accessing local variables and indicating
 155     // where their live ranges ought to be. Data flow between local accesses is
 156     // implicit. Liveness is only explicit at block heads (variablesAtHead).
 157     // This is only used by the DFG simplifier and is only preserved by same.
 158     //
 159     // For example, LoadStore form gives no easy way to determine which SetLocal's
 160     // flow into a GetLocal. As well, LoadStore form implies no restrictions on
 161     // redundancy: you can freely emit multiple GetLocals, or multiple SetLocals
 162     // (or any combination thereof) to the same local in the same block. LoadStore
 163     // form does not require basic blocks to declare how they affect or use locals,
 164     // other than implicitly by using the local ops and by preserving
 165     // variablesAtHead. Finally, LoadStore allows flexibility in how liveness of
 166     // locals is extended; for example you can replace a GetLocal with a Phantom
 167     // and so long as the Phantom retains the GetLocal's children (i.e. the Phi
 168     // most likely) then it implies that the local is still live but that it need
 169     // not be stored to the stack necessarily. This implies that Phantom can
 170     // reference nodes that have no result, as long as those nodes are valid
 171     // GetLocal children (i.e. Phi, SetLocal, SetArgument).
 172     //
 173     // LoadStore form also implies that Phis need not have children. By default,
 174     // they end up having no children if you enter LoadStore using the canonical
 175     // way (call Graph::dethread).
 176     //
 177     // LoadStore form is suitable for CFG transformations, as well as strength
 178     // reduction, folding, and CSE.
 179     LoadStore,
 180
 181     // ThreadedCPS form means that basic blocks list up-front which locals they
 182     // expect to be live at the head, and which locals they make available at the
 183     // tail. ThreadedCPS form also implies that:
 184     //
 185     // - GetLocals and SetLocals to uncaptured variables are not redundant within
 186     //   a basic block.
 187     //
 188     // - All GetLocals and Flushes are linked directly to the last access point
 189     //   of the variable, which must not be another GetLocal if the variable is
 190     //   uncaptured.
 191     //
 192     // - Phantom(Phi) is not legal, but PhantomLocal is.
 193     //
 194     // ThreadedCPS form is suitable for data flow analysis (CFA, prediction
 195     // propagation), register allocation, and code generation.
 196     ThreadedCPS,
 197
 198     // SSA form. See DFGSSAConversionPhase.h for a description.
 199     SSA
 200 };
 201
 202 // Describes the state of the UnionFind structure of VariableAccessData's.
 203 enum UnificationState {
 204     // BasicBlock-local accesses to variables are appropriately unified with each other.
 205     LocallyUnified,
 206
 207     // Unification has been performed globally.
 208     GloballyUnified
 209 };
 210
 211 // Describes how reference counts in the graph behave.
 212 enum RefCountState {
 213     // Everything has refCount() == 1.
 214     EverythingIsLive,
 215
 216     // Set after DCE has run.
 217     ExactRefCount
 218 };
 219
 220 enum OperandSpeculationMode { AutomaticOperandSpeculation, ManualOperandSpeculation };
 221
 222 enum ProofStatus { NeedsCheck, IsProved };
 223
 224 inline bool isProved(ProofStatus proofStatus)
 225 {
 226     ASSERT(proofStatus == IsProved || proofStatus == NeedsCheck);
 227     return proofStatus == IsProved;
 228 }
 229
 230 inline ProofStatus proofStatusForIsProved(bool isProved)
 231 {
 232     return isProved ? IsProved : NeedsCheck;
 233 }
 234
 235 enum KillStatus { DoesNotKill, DoesKill };
 236
 237 inline bool doesKill(KillStatus killStatus)
 238 {
 239     ASSERT(killStatus == DoesNotKill || killStatus == DoesKill);
 240     return killStatus == DoesKill;
 241 }
 242
 243 inline KillStatus killStatusForDoesKill(bool doesKill)
 244 {
 245     return doesKill ? DoesKill : DoesNotKill;
 246 }
 247
 248 template<typename T, typename U>
 249 bool checkAndSet(T& left, U right)
 250 {
 251     if (left == right)
 252         return false;
 253     left = right;
 254     return true;
 255 }
 256
 257 // If possible, this will acquire a lock to make sure that if multiple threads
 258 // start crashing at the same time, you get coherent dump output. Use this only
 259 // when you're forcing a crash with diagnostics.
 260 void startCrashing();
 261
 262 } } // namespace JSC::DFG
 263
 264 namespace WTF {
 265
 266 void printInternal(PrintStream&, JSC::DFG::OptimizationFixpointState);
 267 void printInternal(PrintStream&, JSC::DFG::GraphForm);
 268 void printInternal(PrintStream&, JSC::DFG::UnificationState);
 269 void printInternal(PrintStream&, JSC::DFG::RefCountState);
 270 void printInternal(PrintStream&, JSC::DFG::ProofStatus);
 271
 272 } // namespace WTF
 273
 274 #endif // ENABLE(DFG_JIT)
 275
 276 namespace JSC { namespace DFG {
 277
 278 // Put things here that must be defined even if ENABLE(DFG_JIT) is false.
 279
 280 enum CapabilityLevel {
 281     CannotCompile,
 282     CanInline,
 283     CanCompile,
 284     CanCompileAndInline,
 285     CapabilityLevelNotSet
 286 };
 287
 288 inline bool canCompile(CapabilityLevel level)
 289 {
 290     switch (level) {
 291     case CanCompile:
 292     case CanCompileAndInline:
 293         return true;
 294     default:
 295         return false;
 296     }
 297 }
 298
 299 inline bool canInline(CapabilityLevel level)
 300 {
 301     switch (level) {
 302     case CanInline:
 303     case CanCompileAndInline:
 304         return true;
 305     default:
 306         return false;
 307     }
 308 }
 309
 310 inline CapabilityLevel leastUpperBound(CapabilityLevel a, CapabilityLevel b)
 311 {
 312     switch (a) {
 313     case CannotCompile:
 314         return CannotCompile;
 315     case CanInline:
 316         switch (b) {
 317         case CanInline:
 318         case CanCompileAndInline:
 319             return CanInline;
 320         default:
 321             return CannotCompile;
 322         }
 323     case CanCompile:
 324         switch (b) {
 325         case CanCompile:
 326         case CanCompileAndInline:
 327             return CanCompile;
 328         default:
 329             return CannotCompile;
 330         }
 331     case CanCompileAndInline:
 332         return b;
 333     case CapabilityLevelNotSet:
 334         ASSERT_NOT_REACHED();
 335         return CannotCompile;
 336     }
 337     ASSERT_NOT_REACHED();
 338     return CannotCompile;
 339 }
 340
 341 // Unconditionally disable DFG disassembly support if the DFG is not compiled in.
 342 inline bool shouldShowDisassembly(CompilationMode mode = DFGMode)
 343 {
 344 #if ENABLE(DFG_JIT)
 345     return Options::showDisassembly() || Options::showDFGDisassembly() || (isFTL(mode) && Options::showFTLDisassembly());
 346 #else
 347     UNUSED_PARAM(mode);
 348     return false;
 349 #endif
 350 }
 351
 352 } } // namespace JSC::DFG
 353
 354 #endif // DFGCommon_h
 355