js/src/jit/WarpBuilder.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #ifndef jit_WarpBuilder_h
   8 #define jit_WarpBuilder_h
   9
  10 #include <initializer_list>
  11
  12 #include "ds/InlineTable.h"
  13 #include "jit/JitContext.h"
  14 #include "jit/MIR.h"
  15 #include "jit/WarpBuilderShared.h"
  16 #include "jit/WarpSnapshot.h"
  17 #include "vm/Opcodes.h"
  18
  19 namespace js {
  20 namespace jit {
  21
  22 // JSOps not yet supported by WarpBuilder. See warning at the end of the list.
  23 #define WARP_UNSUPPORTED_OPCODE_LIST(_)  \
  24   /* Intentionally not implemented */    \
  25   _(ForceInterpreter)                    \
  26   /* With */                             \
  27   _(EnterWith)                           \
  28   _(LeaveWith)                           \
  29   /* Eval */                             \
  30   _(Eval)                                \
  31   _(StrictEval)                          \
  32   _(SpreadEval)                          \
  33   _(StrictSpreadEval)                    \
  34   /* Super */                            \
  35   _(SetPropSuper)                        \
  36   _(SetElemSuper)                        \
  37   _(StrictSetPropSuper)                  \
  38   _(StrictSetElemSuper)                  \
  39   /* Compound assignment */              \
  40   _(GetBoundName)                        \
  41   /* Generators / Async (bug 1317690) */ \
  42   _(IsGenClosing)                        \
  43   _(Resume)                              \
  44   /* Misc */                             \
  45   _(DelName)                             \
  46   _(SetIntrinsic)                        \
  47   /* Private Fields */                   \
  48   _(GetAliasedDebugVar)                  \
  49   /* Non-syntactic scope */              \
  50   _(NonSyntacticGlobalThis)              \
  51   /* Records and Tuples */               \
  52   IF_RECORD_TUPLE(_(InitRecord))         \
  53   IF_RECORD_TUPLE(_(AddRecordProperty))  \
  54   IF_RECORD_TUPLE(_(AddRecordSpread))    \
  55   IF_RECORD_TUPLE(_(FinishRecord))       \
  56   IF_RECORD_TUPLE(_(InitTuple))          \
  57   IF_RECORD_TUPLE(_(AddTupleElement))    \
  58   IF_RECORD_TUPLE(_(FinishTuple))        \
  59   // === !! WARNING WARNING WARNING !! ===
  60   // Do you really want to sacrifice performance by not implementing this
  61   // operation in the optimizing compiler?
  62
  63 class MIRGenerator;
  64 class MIRGraph;
  65 class WarpSnapshot;
  66
  67 enum class CacheKind : uint8_t;
  68
  69 // [SMDOC] Control Flow handling in WarpBuilder.
  70 //
  71 // WarpBuilder traverses the script's bytecode and compiles each instruction to
  72 // corresponding MIR instructions. Handling control flow bytecode ops requires
  73 // some special machinery:
  74 //
  75 // Forward branches
  76 // ----------------
  77 // Most branches in the bytecode are forward branches to a JSOp::JumpTarget
  78 // instruction that we have not inspected yet. We compile them in two phases:
  79 //
  80 // 1) When compiling the source instruction: the MBasicBlock is terminated
  81 //    with a control instruction that has a nullptr successor block. We also add
  82 //    a PendingEdge instance to the PendingEdges list for the target bytecode
  83 //    location.
  84 //
  85 // 2) When finally compiling the JSOp::JumpTarget: WarpBuilder::build_JumpTarget
  86 //    creates the target block and uses the list of PendingEdges to 'link' the
  87 //    blocks.
  88 //
  89 // Loops
  90 // -----
  91 // Loops may be nested within other loops, so each WarpBuilder has a LoopState
  92 // stack. This is used to link the backedge to the loop's header block.
  93 //
  94 // Unreachable/dead code
  95 // ---------------------
  96 // Some bytecode instructions never fall through to the next instruction, for
  97 // example JSOp::Return, JSOp::Goto, or JSOp::Throw. Code after such
  98 // instructions is guaranteed to be dead so WarpBuilder skips it until it gets
  99 // to a jump target instruction with pending edges.
 100 //
 101 // Note: The frontend may generate unnecessary JSOp::JumpTarget instructions we
 102 // can ignore when they have no incoming pending edges.
 103 //
 104 // Try-catch
 105 // ---------
 106 // WarpBuilder supports scripts with try-catch by only compiling the try-block
 107 // and bailing out (to the Baseline Interpreter) from the exception handler
 108 // whenever we need to execute the catch-block.
 109 //
 110 // Because we don't compile the catch-block and the code after the try-catch may
 111 // only be reachable via the catch-block, Baseline's BytecodeAnalysis ensures
 112 // Baseline does not attempt OSR into Warp at loops that are only reachable via
 113 // catch/finally blocks.
 114 //
 115 // Finally-blocks are compiled by WarpBuilder, but when we have to enter a
 116 // finally-block from the exception handler, we bail out to the Baseline
 117 // Interpreter.
 118
 119 // PendingEdge is used whenever a block is terminated with a forward branch in
 120 // the bytecode. When we reach the jump target we use this information to link
 121 // the block to the jump target's block.
 122 class PendingEdge {
 123   MBasicBlock* block_;
 124   uint32_t successor_;
 125   uint8_t numToPop_;
 126
 127  public:
 128   PendingEdge(MBasicBlock* block, uint32_t successor, uint32_t numToPop)
 129       : block_(block), successor_(successor), numToPop_(numToPop) {
 130     MOZ_ASSERT(numToPop_ == numToPop, "value must fit in field");
 131   }
 132
 133   MBasicBlock* block() const { return block_; }
 134   uint32_t successor() const { return successor_; }
 135   uint8_t numToPop() const { return numToPop_; }
 136 };
 137
 138 // PendingEdgesMap maps a bytecode instruction to a Vector of PendingEdges
 139 // targeting it. We use InlineMap<> for this because most of the time there are
 140 // only a few pending edges but there can be many when switch-statements are
 141 // involved.
 142 using PendingEdges = Vector<PendingEdge, 2, SystemAllocPolicy>;
 143 using PendingEdgesMap =
 144     InlineMap<jsbytecode*, PendingEdges, 8, PointerHasher<jsbytecode*>,
 145               SystemAllocPolicy>;
 146
 147 // LoopState stores information about a loop that's being compiled to MIR.
 148 class LoopState {
 149   MBasicBlock* header_ = nullptr;
 150
 151  public:
 152   explicit LoopState(MBasicBlock* header) : header_(header) {}
 153
 154   MBasicBlock* header() const { return header_; }
 155 };
 156 using LoopStateStack = Vector<LoopState, 4, JitAllocPolicy>;
 157
 158 // Data that is shared across all WarpBuilders for a given compilation.
 159 class MOZ_STACK_CLASS WarpCompilation {
 160   // The total loop depth, including loops in the caller while
 161   // compiling inlined functions.
 162   uint32_t loopDepth_ = 0;
 163
 164   // Loop phis for iterators that need to be kept alive.
 165   PhiVector iterators_;
 166
 167  public:
 168   explicit WarpCompilation(TempAllocator& alloc) : iterators_(alloc) {}
 169
 170   uint32_t loopDepth() const { return loopDepth_; }
 171   void incLoopDepth() { loopDepth_++; }
 172   void decLoopDepth() {
 173     MOZ_ASSERT(loopDepth() > 0);
 174     loopDepth_--;
 175   }
 176
 177   PhiVector* iterators() { return &iterators_; }
 178 };
 179
 180 // WarpBuilder builds a MIR graph from WarpSnapshot. Unlike WarpOracle,
 181 // WarpBuilder can run off-thread.
 182 class MOZ_STACK_CLASS WarpBuilder : public WarpBuilderShared {
 183   WarpCompilation* warpCompilation_;
 184   MIRGraph& graph_;
 185   const CompileInfo& info_;
 186   const WarpScriptSnapshot* scriptSnapshot_;
 187   JSScript* script_;
 188
 189   // Pointer to a WarpOpSnapshot or nullptr if we reached the end of the list.
 190   // Because bytecode is compiled from first to last instruction (and
 191   // WarpOpSnapshot is sorted the same way), the iterator always moves forward.
 192   const WarpOpSnapshot* opSnapshotIter_ = nullptr;
 193
 194   // Note: loopStack_ is builder-specific. loopStack_.length is the
 195   // depth relative to the current script.  The overall loop depth is
 196   // stored in the WarpCompilation.
 197   LoopStateStack loopStack_;
 198   PendingEdgesMap pendingEdges_;
 199
 200   // These are only initialized when building an inlined script.
 201   WarpBuilder* callerBuilder_ = nullptr;
 202   MResumePoint* callerResumePoint_ = nullptr;
 203   CallInfo* inlineCallInfo_ = nullptr;
 204
 205   WarpCompilation* warpCompilation() const { return warpCompilation_; }
 206   MIRGraph& graph() { return graph_; }
 207   const WarpScriptSnapshot* scriptSnapshot() const { return scriptSnapshot_; }
 208
 209   uint32_t loopDepth() const { return warpCompilation_->loopDepth(); }
 210   void incLoopDepth() { warpCompilation_->incLoopDepth(); }
 211   void decLoopDepth() { warpCompilation_->decLoopDepth(); }
 212   PhiVector* iterators() { return warpCompilation_->iterators(); }
 213
 214   WarpBuilder* callerBuilder() const { return callerBuilder_; }
 215   MResumePoint* callerResumePoint() const { return callerResumePoint_; }
 216
 217   BytecodeSite* newBytecodeSite(BytecodeLocation loc);
 218
 219   const WarpOpSnapshot* getOpSnapshotImpl(BytecodeLocation loc,
 220                                           WarpOpSnapshot::Kind kind);
 221
 222   template <typename T>
 223   const T* getOpSnapshot(BytecodeLocation loc) {
 224     const WarpOpSnapshot* snapshot = getOpSnapshotImpl(loc, T::ThisKind);
 225     return snapshot ? snapshot->as<T>() : nullptr;
 226   }
 227
 228   void initBlock(MBasicBlock* block);
 229   [[nodiscard]] bool startNewEntryBlock(size_t stackDepth,
 230                                         BytecodeLocation loc);
 231   [[nodiscard]] bool startNewBlock(MBasicBlock* predecessor,
 232                                    BytecodeLocation loc, size_t numToPop = 0);
 233   [[nodiscard]] bool startNewLoopHeaderBlock(BytecodeLocation loopHead);
 234   [[nodiscard]] bool startNewOsrPreHeaderBlock(BytecodeLocation loopHead);
 235
 236   bool hasTerminatedBlock() const { return current == nullptr; }
 237   void setTerminatedBlock() { current = nullptr; }
 238
 239   [[nodiscard]] bool addPendingEdge(BytecodeLocation target, MBasicBlock* block,
 240                                     uint32_t successor, uint32_t numToPop = 0);
 241   [[nodiscard]] bool buildForwardGoto(BytecodeLocation target);
 242   [[nodiscard]] bool buildBackedge();
 243   [[nodiscard]] bool buildTestBackedge(BytecodeLocation loc);
 244
 245   [[nodiscard]] bool addIteratorLoopPhis(BytecodeLocation loopHead);
 246
 247   [[nodiscard]] bool buildPrologue();
 248   [[nodiscard]] bool buildBody();
 249
 250   [[nodiscard]] bool buildInlinePrologue();
 251
 252   [[nodiscard]] bool buildIC(BytecodeLocation loc, CacheKind kind,
 253                              std::initializer_list<MDefinition*> inputs);
 254   [[nodiscard]] bool buildBailoutForColdIC(BytecodeLocation loc,
 255                                            CacheKind kind);
 256
 257   [[nodiscard]] bool buildEnvironmentChain();
 258   MInstruction* buildNamedLambdaEnv(MDefinition* callee, MDefinition* env,
 259                                     NamedLambdaObject* templateObj);
 260   MInstruction* buildCallObject(MDefinition* callee, MDefinition* env,
 261                                 CallObject* templateObj);
 262   MInstruction* buildLoadSlot(MDefinition* obj, uint32_t numFixedSlots,
 263                               uint32_t slot);
 264
 265   MConstant* globalLexicalEnvConstant();
 266   MDefinition* getCallee();
 267
 268   [[nodiscard]] bool buildUnaryOp(BytecodeLocation loc);
 269   [[nodiscard]] bool buildBinaryOp(BytecodeLocation loc);
 270   [[nodiscard]] bool buildCompareOp(BytecodeLocation loc);
 271   [[nodiscard]] bool buildTestOp(BytecodeLocation loc);
 272   [[nodiscard]] bool buildCallOp(BytecodeLocation loc);
 273
 274   [[nodiscard]] bool buildInitPropGetterSetterOp(BytecodeLocation loc);
 275   [[nodiscard]] bool buildInitElemGetterSetterOp(BytecodeLocation loc);
 276
 277   [[nodiscard]] bool buildSuspend(BytecodeLocation loc, MDefinition* gen,
 278                                   MDefinition* retVal);
 279
 280   void buildCheckLexicalOp(BytecodeLocation loc);
 281
 282   bool usesEnvironmentChain() const;
 283   MDefinition* walkEnvironmentChain(uint32_t numHops);
 284
 285   void buildCreateThis(CallInfo& callInfo);
 286
 287   [[nodiscard]] bool transpileCall(BytecodeLocation loc,
 288                                    const WarpCacheIR* cacheIRSnapshot,
 289                                    CallInfo* callInfo);
 290
 291   [[nodiscard]] bool buildInlinedCall(BytecodeLocation loc,
 292                                       const WarpInlinedCall* snapshot,
 293                                       CallInfo& callInfo);
 294
 295   MDefinition* patchInlinedReturns(CompileInfo* calleeCompileInfo,
 296                                    CallInfo& callInfo, MIRGraphReturns& exits,
 297                                    MBasicBlock* returnBlock);
 298   MDefinition* patchInlinedReturn(CompileInfo* calleeCompileInfo,
 299                                   CallInfo& callInfo, MBasicBlock* exit,
 300                                   MBasicBlock* returnBlock);
 301
 302 #define BUILD_OP(OP, ...) [[nodiscard]] bool build_##OP(BytecodeLocation loc);
 303   FOR_EACH_OPCODE(BUILD_OP)
 304 #undef BUILD_OP
 305
 306  public:
 307   WarpBuilder(WarpSnapshot& snapshot, MIRGenerator& mirGen,
 308               WarpCompilation* warpCompilation);
 309   WarpBuilder(WarpBuilder* caller, WarpScriptSnapshot* snapshot,
 310               CompileInfo& compileInfo, CallInfo* inlineCallInfo,
 311               MResumePoint* callerResumePoint);
 312
 313   [[nodiscard]] bool build();
 314   [[nodiscard]] bool buildInline();
 315
 316   const CompileInfo& info() const { return info_; }
 317   CallInfo* inlineCallInfo() const { return inlineCallInfo_; }
 318 };
 319
 320 }  // namespace jit
 321 }  // namespace js
 322
 323 #endif /* jit_WarpBuilder_h */