DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Implementation

Mercurial (777e60ca8853)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set ts=8 sts=4 et sw=4 tw=99:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef jit_IonBuilder_h
#define jit_IonBuilder_h

#ifdef JS_ION

// This file declares the data structures for building a MIRGraph from a
// JSScript.

#include "jit/BytecodeAnalysis.h"
#include "jit/IonOptimizationLevels.h"
#include "jit/MIR.h"
#include "jit/MIRGenerator.h"
#include "jit/MIRGraph.h"
#include "jit/TypeDescrSet.h"

namespace js {
namespace jit {

class CodeGenerator;
class CallInfo;
class BaselineInspector;
class BaselineFrameInspector;

// Records information about a baseline frame for compilation that is stable
// when later used off thread.
BaselineFrameInspector*
NewBaselineFrameInspector(TempAllocator* temp, BaselineFrame* frame, CompileInfo* info);

class IonBuilder : public MIRGenerator
{
    enum ControlStatus {
        ControlStatus_Error,
        ControlStatus_Abort,
        ControlStatus_Ended,        // There is no continuation/join point.
        ControlStatus_Joined,       // Created a join node.
        ControlStatus_Jumped,       // Parsing another branch at the same level.
        ControlStatus_None          // No control flow.
    };

    enum SetElemSafety {
        // Normal write like a[b] = c.
        SetElem_Normal,

        // Write due to UnsafePutElements:
        // - assumed to be in bounds,
        // - not checked for data races
        SetElem_Unsafe,
    };

    struct DeferredEdge : public TempObject
    {
        MBasicBlock* block;
        DeferredEdge* next;

        DeferredEdge(MBasicBlock* block, DeferredEdge* next)
          : block(block), next(next)
        { }
    };

    struct ControlFlowInfo {
        // Entry in the cfgStack.
        uint32_t cfgEntry;

        // Label that continues go to.
        jsbytecode* continuepc;

        ControlFlowInfo(uint32_t cfgEntry, jsbytecode* continuepc)
          : cfgEntry(cfgEntry),
            continuepc(continuepc)
        { }
    };

    // To avoid recursion, the bytecode analyzer uses a stack where each entry
    // is a small state machine. As we encounter branches or jumps in the
    // bytecode, we push information about the edges on the stack so that the
    // CFG can be built in a tree-like fashion.
    struct CFGState {
        enum State {
            IF_TRUE,            // if() { }, no else.
            IF_TRUE_EMPTY_ELSE, // if() { }, empty else
            IF_ELSE_TRUE,       // if() { X } else { }
            IF_ELSE_FALSE,      // if() { } else { X }
            DO_WHILE_LOOP_BODY, // do { x } while ()
            DO_WHILE_LOOP_COND, // do { } while (x)
            WHILE_LOOP_COND,    // while (x) { }
            WHILE_LOOP_BODY,    // while () { x }
            FOR_LOOP_COND,      // for (; x;) { }
            FOR_LOOP_BODY,      // for (; ;) { x }
            FOR_LOOP_UPDATE,    // for (; ; x) { }
            TABLE_SWITCH,       // switch() { x }
            COND_SWITCH_CASE,   // switch() { case X: ... }
            COND_SWITCH_BODY,   // switch() { case ...: X }
            AND_OR,             // && x, || x
            LABEL,              // label: x
            TRY                 // try { x } catch(e) { }
        };

        State state;            // Current state of this control structure.
        jsbytecode* stopAt;     // Bytecode at which to stop the processing loop.

        // For if structures, this contains branch information.
        union {
            struct {
                MBasicBlock* ifFalse;
                jsbytecode* falseEnd;
                MBasicBlock* ifTrue;    // Set when the end of the true path is reached.
                MTest* test;
            } branch;
            struct {
                // Common entry point.
                MBasicBlock* entry;

                // Whether OSR is being performed for this loop.
                bool osr;

                // Position of where the loop body starts and ends.
                jsbytecode* bodyStart;
                jsbytecode* bodyEnd;

                // pc immediately after the loop exits.
                jsbytecode* exitpc;

                // pc for 'continue' jumps.
                jsbytecode* continuepc;

                // Common exit point. Created lazily, so it may be nullptr.
                MBasicBlock* successor;

                // Deferred break and continue targets.
                DeferredEdge* breaks;
                DeferredEdge* continues;

                // Initial state, in case loop processing is restarted.
                State initialState;
                jsbytecode* initialPc;
                jsbytecode* initialStopAt;
                jsbytecode* loopHead;

                // For-loops only.
                jsbytecode* condpc;
                jsbytecode* updatepc;
                jsbytecode* updateEnd;
            } loop;
            struct {
                // pc immediately after the switch.
                jsbytecode* exitpc;

                // Deferred break and continue targets.
                DeferredEdge* breaks;

                // MIR instruction
                MTableSwitch* ins;

                // The number of current successor that get mapped into a block.
                uint32_t currentBlock;

            } tableswitch;
            struct {
                // Vector of body blocks to process after the cases.
                FixedList<MBasicBlock*>* bodies;

                // When processing case statements, this counter points at the
                // last uninitialized body.  When processing bodies, this
                // counter targets the next body to process.
                uint32_t currentIdx;

                // Remember the block index of the default case.
                jsbytecode* defaultTarget;
                uint32_t defaultIdx;

                // Block immediately after the switch.
                jsbytecode* exitpc;
                DeferredEdge* breaks;
            } condswitch;
            struct {
                DeferredEdge* breaks;
            } label;
            struct {
                MBasicBlock* successor;
            } try_;
        };

        inline bool isLoop() const {
            switch (state) {
              case DO_WHILE_LOOP_COND:
              case DO_WHILE_LOOP_BODY:
              case WHILE_LOOP_COND:
              case WHILE_LOOP_BODY:
              case FOR_LOOP_COND:
              case FOR_LOOP_BODY:
              case FOR_LOOP_UPDATE:
                return true;
              default:
                return false;
            }
        }

        static CFGState If(jsbytecode* join, MTest* test);
        static CFGState IfElse(jsbytecode* trueEnd, jsbytecode* falseEnd, MTest* test);
        static CFGState AndOr(jsbytecode* join, MBasicBlock* joinStart);
        static CFGState TableSwitch(jsbytecode* exitpc, MTableSwitch* ins);
        static CFGState CondSwitch(IonBuilder* builder, jsbytecode* exitpc, jsbytecode* defaultTarget);
        static CFGState Label(jsbytecode* exitpc);
        static CFGState Try(jsbytecode* exitpc, MBasicBlock* successor);
    };

    static int CmpSuccessors(const void* a, const void* b);

  public:
    IonBuilder(JSContext* analysisContext, CompileCompartment* comp,
               const JitCompileOptions& options, TempAllocator* temp,
               MIRGraph* graph, types::CompilerConstraintList* constraints,
               BaselineInspector* inspector, CompileInfo* info,
               const OptimizationInfo* optimizationInfo, BaselineFrameInspector* baselineFrame,
               size_t inliningDepth = 0, uint32_t loopDepth = 0);

    bool build();
    bool buildInline(IonBuilder* callerBuilder, MResumePoint* callerResumePoint,
                     CallInfo& callInfo);

  private:
    bool traverseBytecode();
    ControlStatus snoopControlFlow(JSOp op);
    bool processIterators();
    bool inspectOpcode(JSOp op);
    uint32_t readIndex(jsbytecode* pc);
    JSAtom* readAtom(jsbytecode* pc);
    bool abort(const char* message, ...);
    void spew(const char* message);

    JSFunction* getSingleCallTarget(types::TemporaryTypeSet* calleeTypes);
    bool getPolyCallTargets(types::TemporaryTypeSet* calleeTypes, bool constructing,
                            ObjectVector& targets, uint32_t maxTargets, bool* gotLambda);

    void popCfgStack();
    DeferredEdge* filterDeadDeferredEdges(DeferredEdge* edge);
    bool processDeferredContinues(CFGState& state);
    ControlStatus processControlEnd();
    ControlStatus processCfgStack();
    ControlStatus processCfgEntry(CFGState& state);
    ControlStatus processIfEnd(CFGState& state);
    ControlStatus processIfElseTrueEnd(CFGState& state);
    ControlStatus processIfElseFalseEnd(CFGState& state);
    ControlStatus processDoWhileBodyEnd(CFGState& state);
    ControlStatus processDoWhileCondEnd(CFGState& state);
    ControlStatus processWhileCondEnd(CFGState& state);
    ControlStatus processWhileBodyEnd(CFGState& state);
    ControlStatus processForCondEnd(CFGState& state);
    ControlStatus processForBodyEnd(CFGState& state);
    ControlStatus processForUpdateEnd(CFGState& state);
    ControlStatus processNextTableSwitchCase(CFGState& state);
    ControlStatus processCondSwitchCase(CFGState& state);
    ControlStatus processCondSwitchBody(CFGState& state);
    ControlStatus processSwitchBreak(JSOp op);
    ControlStatus processSwitchEnd(DeferredEdge* breaks, jsbytecode* exitpc);
    ControlStatus processAndOrEnd(CFGState& state);
    ControlStatus processLabelEnd(CFGState& state);
    ControlStatus processTryEnd(CFGState& state);
    ControlStatus processReturn(JSOp op);
    ControlStatus processThrow();
    ControlStatus processContinue(JSOp op);
    ControlStatus processBreak(JSOp op, jssrcnote* sn);
    ControlStatus maybeLoop(JSOp op, jssrcnote* sn);
    bool pushLoop(CFGState::State state, jsbytecode* stopAt, MBasicBlock* entry, bool osr,
                  jsbytecode* loopHead, jsbytecode* initialPc,
                  jsbytecode* bodyStart, jsbytecode* bodyEnd, jsbytecode* exitpc,
                  jsbytecode* continuepc = nullptr);
    bool analyzeNewLoopTypes(MBasicBlock* entry, jsbytecode* start, jsbytecode* end);

    MBasicBlock* addBlock(MBasicBlock* block, uint32_t loopDepth);
    MBasicBlock* newBlock(MBasicBlock* predecessor, jsbytecode* pc);
    MBasicBlock* newBlock(MBasicBlock* predecessor, jsbytecode* pc, uint32_t loopDepth);
    MBasicBlock* newBlock(MBasicBlock* predecessor, jsbytecode* pc, MResumePoint* priorResumePoint);
    MBasicBlock* newBlockPopN(MBasicBlock* predecessor, jsbytecode* pc, uint32_t popped);
    MBasicBlock* newBlockAfter(MBasicBlock* at, MBasicBlock* predecessor, jsbytecode* pc);
    MBasicBlock* newOsrPreheader(MBasicBlock* header, jsbytecode* loopEntry);
    MBasicBlock* newPendingLoopHeader(MBasicBlock* predecessor, jsbytecode* pc, bool osr, bool canOsr,
                                      unsigned stackPhiCount);
    MBasicBlock* newBlock(jsbytecode* pc) {
        return newBlock(nullptr, pc);
    }
    MBasicBlock* newBlockAfter(MBasicBlock* at, jsbytecode* pc) {
        return newBlockAfter(at, nullptr, pc);
    }

    // Given a list of pending breaks, creates a new block and inserts a Goto
    // linking each break to the new block.
    MBasicBlock* createBreakCatchBlock(DeferredEdge* edge, jsbytecode* pc);

    // Finishes loops that do not actually loop, containing only breaks and
    // returns or a do while loop with a condition that is constant false.
    ControlStatus processBrokenLoop(CFGState& state);

    // Computes loop phis, places them in all successors of a loop, then
    // handles any pending breaks.
    ControlStatus finishLoop(CFGState& state, MBasicBlock* successor);

    // Incorporates a type/typeSet into an OSR value for a loop, after the loop
    // body has been processed.
    bool addOsrValueTypeBarrier(uint32_t slot, MInstruction** def,
                                MIRType type, types::TemporaryTypeSet* typeSet);
    bool maybeAddOsrTypeBarriers();

    // Restarts processing of a loop if the type information at its header was
    // incomplete.
    ControlStatus restartLoop(CFGState state);

    void assertValidLoopHeadOp(jsbytecode* pc);

    ControlStatus forLoop(JSOp op, jssrcnote* sn);
    ControlStatus whileOrForInLoop(jssrcnote* sn);
    ControlStatus doWhileLoop(JSOp op, jssrcnote* sn);
    ControlStatus tableSwitch(JSOp op, jssrcnote* sn);
    ControlStatus condSwitch(JSOp op, jssrcnote* sn);

    // Please see the Big Honkin' Comment about how resume points work in
    // IonBuilder.cpp, near the definition for this function.
    bool resume(MInstruction* ins, jsbytecode* pc, MResumePoint::Mode mode);
    bool resumeAt(MInstruction* ins, jsbytecode* pc);
    bool resumeAfter(MInstruction* ins);
    bool maybeInsertResume();

    void insertRecompileCheck();

    void initParameters();
    void rewriteParameter(uint32_t slotIdx, MDefinition* param, int32_t argIndex);
    void rewriteParameters();
    bool initScopeChain(MDefinition* callee = nullptr);
    bool initArgumentsObject();
    bool pushConstant(const Value& v);

    MConstant* constant(const Value& v);
    MConstant* constantInt(int32_t i);

    // Filter the type information at tests
    bool filterTypesAtTest(MTest* test);

    // Add a guard which ensure that the set of type which goes through this
    // generated code correspond to the observed types for the bytecode.
    bool pushTypeBarrier(MDefinition* def, types::TemporaryTypeSet* observed, bool needBarrier);

    // As pushTypeBarrier, but will compute the needBarrier boolean itself based
    // on observed and the JSFunction that we're planning to call. The
    // JSFunction must be a DOM method or getter.
    bool pushDOMTypeBarrier(MInstruction* ins, types::TemporaryTypeSet* observed, JSFunction* func);

    // If definiteType is not known or def already has the right type, just
    // returns def.  Otherwise, returns an MInstruction that has that definite
    // type, infallibly unboxing ins as needed.  The new instruction will be
    // added to |current| in this case.
    MDefinition* ensureDefiniteType(MDefinition* def, MIRType definiteType);

    // Creates a MDefinition based on the given def improved with type as TypeSet.
    MDefinition* ensureDefiniteTypeSet(MDefinition* def, types::TemporaryTypeSet* types);

    JSObject* getSingletonPrototype(JSFunction* target);

    MDefinition* createThisScripted(MDefinition* callee);
    MDefinition* createThisScriptedSingleton(JSFunction* target, MDefinition* callee);
    MDefinition* createThis(JSFunction* target, MDefinition* callee);
    MInstruction* createDeclEnvObject(MDefinition* callee, MDefinition* scopeObj);
    MInstruction* createCallObject(MDefinition* callee, MDefinition* scopeObj);

    MDefinition* walkScopeChain(unsigned hops);

    MInstruction* addConvertElementsToDoubles(MDefinition* elements);
    MInstruction* addBoundsCheck(MDefinition* index, MDefinition* length);
    MInstruction* addShapeGuard(MDefinition* obj, Shape* const shape, BailoutKind bailoutKind);

    MDefinition* convertShiftToMaskForStaticTypedArray(MDefinition* id,
                                                       ArrayBufferView::ViewType viewType);

    bool invalidatedIdempotentCache();

    bool hasStaticScopeObject(ScopeCoordinate sc, JSObject** pcall);
    bool loadSlot(MDefinition* obj, size_t slot, size_t nfixed, MIRType rvalType,
                  bool barrier, types::TemporaryTypeSet* types);
    bool loadSlot(MDefinition* obj, Shape* shape, MIRType rvalType,
                  bool barrier, types::TemporaryTypeSet* types);
    bool storeSlot(MDefinition* obj, size_t slot, size_t nfixed,
                   MDefinition* value, bool needsBarrier,
                   MIRType slotType = MIRType_None);
    bool storeSlot(MDefinition* obj, Shape* shape, MDefinition* value, bool needsBarrier,
                   MIRType slotType = MIRType_None);

    // jsop_getprop() helpers.
    bool getPropTryArgumentsLength(bool* emitted);
    bool getPropTryConstant(bool* emitted, PropertyName* name,
                            types::TemporaryTypeSet* types);
    bool getPropTryDefiniteSlot(bool* emitted, PropertyName* name,
                                bool barrier, types::TemporaryTypeSet* types);
    bool getPropTryCommonGetter(bool* emitted, PropertyName* name,
                                types::TemporaryTypeSet* types);
    bool getPropTryInlineAccess(bool* emitted, PropertyName* name,
                                bool barrier, types::TemporaryTypeSet* types);
    bool getPropTryTypedObject(bool* emitted, PropertyName* name,
                               types::TemporaryTypeSet* resultTypes);
    bool getPropTryScalarPropOfTypedObject(bool* emitted,
                                           int32_t fieldOffset,
                                           TypeDescrSet fieldTypeReprs,
                                           types::TemporaryTypeSet* resultTypes);
    bool getPropTryComplexPropOfTypedObject(bool* emitted,
                                            int32_t fieldOffset,
                                            TypeDescrSet fieldTypeReprs,
                                            size_t fieldIndex,
                                            types::TemporaryTypeSet* resultTypes);
    bool getPropTryCache(bool* emitted, PropertyName* name,
                         bool barrier, types::TemporaryTypeSet* types);
    bool needsToMonitorMissingProperties(types::TemporaryTypeSet* types);

    // jsop_setprop() helpers.
    bool setPropTryCommonSetter(bool* emitted, MDefinition* obj,
                                PropertyName* name, MDefinition* value);
    bool setPropTryCommonDOMSetter(bool* emitted, MDefinition* obj,
                                   MDefinition* value, JSFunction* setter,
                                   bool isDOM);
    bool setPropTryDefiniteSlot(bool* emitted, MDefinition* obj,
                                PropertyName* name, MDefinition* value,
                                bool barrier, types::TemporaryTypeSet* objTypes);
    bool setPropTryInlineAccess(bool* emitted, MDefinition* obj,
                                PropertyName* name, MDefinition* value, bool barrier,
                                types::TemporaryTypeSet* objTypes);
    bool setPropTryTypedObject(bool* emitted, MDefinition* obj,
                               PropertyName* name, MDefinition* value);
    bool setPropTryScalarPropOfTypedObject(bool* emitted,
                                           MDefinition* obj,
                                           int32_t fieldOffset,
                                           MDefinition* value,
                                           TypeDescrSet fieldTypeReprs);
    bool setPropTryCache(bool* emitted, MDefinition* obj,
                         PropertyName* name, MDefinition* value,
                         bool barrier, types::TemporaryTypeSet* objTypes);

    // binary data lookup helpers.
    bool lookupTypeDescrSet(MDefinition* typedObj,
                                     TypeDescrSet* out);
    bool typeSetToTypeDescrSet(types::TemporaryTypeSet* types,
                                        TypeDescrSet* out);
    bool lookupTypedObjectField(MDefinition* typedObj,
                                PropertyName* name,
                                int32_t* fieldOffset,
                                TypeDescrSet* fieldTypeReprs,
                                size_t* fieldIndex);
    MDefinition* loadTypedObjectType(MDefinition* value);
    void loadTypedObjectData(MDefinition* typedObj,
                             MDefinition* offset,
                             bool canBeNeutered,
                             MDefinition** owner,
                             MDefinition** ownerOffset);
    void loadTypedObjectElements(MDefinition* typedObj,
                                 MDefinition* offset,
                                 int32_t unit,
                                 bool canBeNeutered,
                                 MDefinition** ownerElements,
                                 MDefinition** ownerScaledOffset);
    MDefinition* typeObjectForElementFromArrayStructType(MDefinition* typedObj);
    MDefinition* typeObjectForFieldFromStructType(MDefinition* type,
                                                  size_t fieldIndex);
    bool storeScalarTypedObjectValue(MDefinition* typedObj,
                                     MDefinition* offset,
                                     ScalarTypeDescr::Type type,
                                     bool canBeNeutered,
                                     bool racy,
                                     MDefinition* value);
    bool checkTypedObjectIndexInBounds(int32_t elemSize,
                                       MDefinition* obj,
                                       MDefinition* index,
                                       TypeDescrSet objTypeDescrs,
                                       MDefinition** indexAsByteOffset,
                                       bool* canBeNeutered);
    bool pushDerivedTypedObject(bool* emitted,
                                MDefinition* obj,
                                MDefinition* offset,
                                TypeDescrSet derivedTypeDescrs,
                                MDefinition* derivedTypeObj,
                                bool canBeNeutered);
    bool pushScalarLoadFromTypedObject(bool* emitted,
                                       MDefinition* obj,
                                       MDefinition* offset,
                                       ScalarTypeDescr::Type type,
                                       bool canBeNeutered);
    MDefinition* neuterCheck(MDefinition* obj);

    // jsop_setelem() helpers.
    bool setElemTryTypedArray(bool* emitted, MDefinition* object,
                         MDefinition* index, MDefinition* value);
    bool setElemTryTypedObject(bool* emitted, MDefinition* obj,
                               MDefinition* index, MDefinition* value);
    bool setElemTryTypedStatic(bool* emitted, MDefinition* object,
                               MDefinition* index, MDefinition* value);
    bool setElemTryDense(bool* emitted, MDefinition* object,
                         MDefinition* index, MDefinition* value);
    bool setElemTryArguments(bool* emitted, MDefinition* object,
                             MDefinition* index, MDefinition* value);
    bool setElemTryCache(bool* emitted, MDefinition* object,
                         MDefinition* index, MDefinition* value);
    bool setElemTryScalarElemOfTypedObject(bool* emitted,
                                           MDefinition* obj,
                                           MDefinition* index,
                                           TypeDescrSet objTypeReprs,
                                           MDefinition* value,
                                           TypeDescrSet elemTypeReprs,
                                           int32_t elemSize);

    // jsop_getelem() helpers.
    bool getElemTryDense(bool* emitted, MDefinition* obj, MDefinition* index);
    bool getElemTryTypedStatic(bool* emitted, MDefinition* obj, MDefinition* index);
    bool getElemTryTypedArray(bool* emitted, MDefinition* obj, MDefinition* index);
    bool getElemTryTypedObject(bool* emitted, MDefinition* obj, MDefinition* index);
    bool getElemTryString(bool* emitted, MDefinition* obj, MDefinition* index);
    bool getElemTryArguments(bool* emitted, MDefinition* obj, MDefinition* index);
    bool getElemTryArgumentsInlined(bool* emitted, MDefinition* obj, MDefinition* index);
    bool getElemTryCache(bool* emitted, MDefinition* obj, MDefinition* index);
    bool getElemTryScalarElemOfTypedObject(bool* emitted,
                                           MDefinition* obj,
                                           MDefinition* index,
                                           TypeDescrSet objTypeReprs,
                                           TypeDescrSet elemTypeReprs,
                                           int32_t elemSize);
    bool getElemTryComplexElemOfTypedObject(bool* emitted,
                                            MDefinition* obj,
                                            MDefinition* index,
                                            TypeDescrSet objTypeReprs,
                                            TypeDescrSet elemTypeReprs,
                                            int32_t elemSize);

    enum BoundsChecking { DoBoundsCheck, SkipBoundsCheck };

    // Add instructions to compute a typed array's length and data.  Also
    // optionally convert |*index| into a bounds-checked definition, if
    // requested.
    //
    // If you only need the array's length, use addTypedArrayLength below.
    void addTypedArrayLengthAndData(MDefinition* obj,
                                    BoundsChecking checking,
                                    MDefinition** index,
                                    MInstruction** length, MInstruction** elements);

    // Add an instruction to compute a typed array's length to the current
    // block.  If you also need the typed array's data, use the above method
    // instead.
    MInstruction* addTypedArrayLength(MDefinition* obj) {
        MInstruction* length;
        addTypedArrayLengthAndData(obj, SkipBoundsCheck, nullptr, &length, nullptr);
        return length;
    }


    MDefinition* getCallee();

    bool jsop_add(MDefinition* left, MDefinition* right);
    bool jsop_bitnot();
    bool jsop_bitop(JSOp op);
    bool jsop_binary(JSOp op);
    bool jsop_binary(JSOp op, MDefinition* left, MDefinition* right);
    bool jsop_pos();
    bool jsop_neg();
    bool jsop_setarg(uint32_t arg);
    bool jsop_defvar(uint32_t index);
    bool jsop_deffun(uint32_t index);
    bool jsop_notearg();
    bool jsop_funcall(uint32_t argc);
    bool jsop_funapply(uint32_t argc);
    bool jsop_funapplyarguments(uint32_t argc);
    bool jsop_call(uint32_t argc, bool constructing);
    bool jsop_eval(uint32_t argc);
    bool jsop_ifeq(JSOp op);
    bool jsop_try();
    bool jsop_label();
    bool jsop_condswitch();
    bool jsop_andor(JSOp op);
    bool jsop_dup2();
    bool jsop_loophead(jsbytecode* pc);
    bool jsop_compare(JSOp op);
    bool getStaticName(JSObject* staticObject, PropertyName* name, bool* psucceeded);
    bool setStaticName(JSObject* staticObject, PropertyName* name);
    bool jsop_getgname(PropertyName* name);
    bool jsop_getname(PropertyName* name);
    bool jsop_intrinsic(PropertyName* name);
    bool jsop_bindname(PropertyName* name);
    bool jsop_getelem();
    bool jsop_getelem_dense(MDefinition* obj, MDefinition* index);
    bool jsop_getelem_typed(MDefinition* obj, MDefinition* index, ScalarTypeDescr::Type arrayType);
    bool jsop_setelem();
    bool jsop_setelem_dense(types::TemporaryTypeSet::DoubleConversion conversion,
                            SetElemSafety safety,
                            MDefinition* object, MDefinition* index, MDefinition* value);
    bool jsop_setelem_typed(ScalarTypeDescr::Type arrayType,
                            SetElemSafety safety,
                            MDefinition* object, MDefinition* index, MDefinition* value);
    bool jsop_setelem_typed_object(ScalarTypeDescr::Type arrayType,
                                   SetElemSafety safety, bool racy,
                                   MDefinition* object, MDefinition* index, MDefinition* value);
    bool jsop_length();
    bool jsop_length_fastPath();
    bool jsop_arguments();
    bool jsop_arguments_length();
    bool jsop_arguments_getelem();
    bool jsop_runonce();
    bool jsop_rest();
    bool jsop_not();
    bool jsop_getprop(PropertyName* name);
    bool jsop_setprop(PropertyName* name);
    bool jsop_delprop(PropertyName* name);
    bool jsop_delelem();
    bool jsop_newarray(uint32_t count);
    bool jsop_newobject();
    bool jsop_initelem();
    bool jsop_initelem_array();
    bool jsop_initelem_getter_setter();
    bool jsop_mutateproto();
    bool jsop_initprop(PropertyName* name);
    bool jsop_initprop_getter_setter(PropertyName* name);
    bool jsop_regexp(RegExpObject* reobj);
    bool jsop_object(JSObject* obj);
    bool jsop_lambda(JSFunction* fun);
    bool jsop_lambda_arrow(JSFunction* fun);
    bool jsop_this();
    bool jsop_typeof();
    bool jsop_toid();
    bool jsop_iter(uint8_t flags);
    bool jsop_iternext();
    bool jsop_itermore();
    bool jsop_iterend();
    bool jsop_in();
    bool jsop_in_dense();
    bool jsop_instanceof();
    bool jsop_getaliasedvar(ScopeCoordinate sc);
    bool jsop_setaliasedvar(ScopeCoordinate sc);

    /* Inlining. */

    enum InliningStatus
    {
        InliningStatus_Error,
        InliningStatus_NotInlined,
        InliningStatus_Inlined
    };

    enum InliningDecision
    {
        InliningDecision_Error,
        InliningDecision_Inline,
        InliningDecision_DontInline
    };

    static InliningDecision DontInline(JSScript* targetScript, const char* reason);

    // Oracles.
    InliningDecision canInlineTarget(JSFunction* target, CallInfo& callInfo);
    InliningDecision makeInliningDecision(JSFunction* target, CallInfo& callInfo);
    bool selectInliningTargets(ObjectVector& targets, CallInfo& callInfo,
                               BoolVector& choiceSet, uint32_t* numInlineable);

    // Native inlining helpers.
    types::TemporaryTypeSet* getInlineReturnTypeSet();
    MIRType getInlineReturnType();

    // Array natives.
    InliningStatus inlineArray(CallInfo& callInfo);
    InliningStatus inlineArrayPopShift(CallInfo& callInfo, MArrayPopShift::Mode mode);
    InliningStatus inlineArrayPush(CallInfo& callInfo);
    InliningStatus inlineArrayConcat(CallInfo& callInfo);
    InliningStatus inlineArraySplice(CallInfo& callInfo);

    // Math natives.
    InliningStatus inlineMathAbs(CallInfo& callInfo);
    InliningStatus inlineMathFloor(CallInfo& callInfo);
    InliningStatus inlineMathCeil(CallInfo& callInfo);
    InliningStatus inlineMathRound(CallInfo& callInfo);
    InliningStatus inlineMathSqrt(CallInfo& callInfo);
    InliningStatus inlineMathAtan2(CallInfo& callInfo);
    InliningStatus inlineMathHypot(CallInfo& callInfo);
    InliningStatus inlineMathMinMax(CallInfo& callInfo, bool max);
    InliningStatus inlineMathPow(CallInfo& callInfo);
    InliningStatus inlineMathRandom(CallInfo& callInfo);
    InliningStatus inlineMathImul(CallInfo& callInfo);
    InliningStatus inlineMathFRound(CallInfo& callInfo);
    InliningStatus inlineMathFunction(CallInfo& callInfo, MMathFunction::Function function);

    // String natives.
    InliningStatus inlineStringObject(CallInfo& callInfo);
    InliningStatus inlineStringSplit(CallInfo& callInfo);
    InliningStatus inlineStrCharCodeAt(CallInfo& callInfo);
    InliningStatus inlineStrFromCharCode(CallInfo& callInfo);
    InliningStatus inlineStrCharAt(CallInfo& callInfo);
    InliningStatus inlineStrReplace(CallInfo& callInfo);

    // RegExp natives.
    InliningStatus inlineRegExpExec(CallInfo& callInfo);
    InliningStatus inlineRegExpTest(CallInfo& callInfo);

    // Array intrinsics.
    InliningStatus inlineUnsafePutElements(CallInfo& callInfo);
    bool inlineUnsafeSetDenseArrayElement(CallInfo& callInfo, uint32_t base);
    bool inlineUnsafeSetTypedArrayElement(CallInfo& callInfo, uint32_t base,
                                          ScalarTypeDescr::Type arrayType);
    bool inlineUnsafeSetTypedObjectArrayElement(CallInfo& callInfo, uint32_t base,
                                                ScalarTypeDescr::Type arrayType);
    InliningStatus inlineNewDenseArray(CallInfo& callInfo);
    InliningStatus inlineNewDenseArrayForSequentialExecution(CallInfo& callInfo);
    InliningStatus inlineNewDenseArrayForParallelExecution(CallInfo& callInfo);

    // Slot intrinsics.
    InliningStatus inlineUnsafeSetReservedSlot(CallInfo& callInfo);
    InliningStatus inlineUnsafeGetReservedSlot(CallInfo& callInfo);

    // ForkJoin intrinsics
    InliningStatus inlineForkJoinGetSlice(CallInfo& callInfo);

    // TypedObject intrinsics.
    InliningStatus inlineObjectIsTypeDescr(CallInfo& callInfo);
    InliningStatus inlineSetTypedObjectOffset(CallInfo& callInfo);
    bool elementAccessIsTypedObjectArrayOfScalarType(MDefinition* obj, MDefinition* id,
                                                     ScalarTypeDescr::Type* arrayType);

    // Utility intrinsics.
    InliningStatus inlineIsCallable(CallInfo& callInfo);
    InliningStatus inlineHaveSameClass(CallInfo& callInfo);
    InliningStatus inlineToObject(CallInfo& callInfo);
    InliningStatus inlineDump(CallInfo& callInfo);
    InliningStatus inlineHasClass(CallInfo& callInfo, const Class* clasp) {
        return inlineHasClasses(callInfo, clasp, nullptr);
    }
    InliningStatus inlineHasClasses(CallInfo& callInfo, const Class* clasp1, const Class* clasp2);

    // Testing functions.
    InliningStatus inlineForceSequentialOrInParallelSection(CallInfo& callInfo);
    InliningStatus inlineBailout(CallInfo& callInfo);
    InliningStatus inlineAssertFloat32(CallInfo& callInfo);

    // Bind function.
    InliningStatus inlineBoundFunction(CallInfo& callInfo, JSFunction* target);

    // Main inlining functions
    InliningStatus inlineNativeCall(CallInfo& callInfo, JSFunction* target);
    bool inlineScriptedCall(CallInfo& callInfo, JSFunction* target);
    InliningStatus inlineSingleCall(CallInfo& callInfo, JSFunction* target);

    // Call functions
    InliningStatus inlineCallsite(ObjectVector& targets, ObjectVector& originals,
                                  bool lambda, CallInfo& callInfo);
    bool inlineCalls(CallInfo& callInfo, ObjectVector& targets, ObjectVector& originals,
                     BoolVector& choiceSet, MGetPropertyCache* maybeCache);

    // Inlining helpers.
    bool inlineGenericFallback(JSFunction* target, CallInfo& callInfo, MBasicBlock* dispatchBlock,
                               bool clonedAtCallsite);
    bool inlineTypeObjectFallback(CallInfo& callInfo, MBasicBlock* dispatchBlock,
                                  MTypeObjectDispatch* dispatch, MGetPropertyCache* cache,
                                  MBasicBlock** fallbackTarget);

    bool testNeedsArgumentCheck(JSFunction* target, CallInfo& callInfo);

    MDefinition* makeCallsiteClone(JSFunction* target, MDefinition* fun);
    MCall* makeCallHelper(JSFunction* target, CallInfo& callInfo, bool cloneAtCallsite);
    bool makeCall(JSFunction* target, CallInfo& callInfo, bool cloneAtCallsite);

    MDefinition* patchInlinedReturn(CallInfo& callInfo, MBasicBlock* exit, MBasicBlock* bottom);
    MDefinition* patchInlinedReturns(CallInfo& callInfo, MIRGraphReturns& returns,
                                     MBasicBlock* bottom);

    bool objectsHaveCommonPrototype(types::TemporaryTypeSet* types, PropertyName* name,
                                    bool isGetter, JSObject* foundProto);
    void freezePropertiesForCommonPrototype(types::TemporaryTypeSet* types, PropertyName* name,
                                            JSObject* foundProto);
    MDefinition* testCommonGetterSetter(types::TemporaryTypeSet* types, PropertyName* name,
                                        bool isGetter, JSObject* foundProto, Shape* lastProperty);
    bool testShouldDOMCall(types::TypeSet* inTypes,
                           JSFunction* func, JSJitInfo::OpType opType);

    bool annotateGetPropertyCache(MDefinition* obj, MGetPropertyCache* getPropCache,
                                  types::TemporaryTypeSet* objTypes,
                                  types::TemporaryTypeSet* pushedTypes);

    MGetPropertyCache* getInlineableGetPropertyCache(CallInfo& callInfo);

    JSObject* testSingletonProperty(JSObject* obj, PropertyName* name);
    bool testSingletonPropertyTypes(MDefinition* obj, JSObject* singleton, PropertyName* name,
                                    bool* testObject, bool* testString);
    bool getDefiniteSlot(types::TemporaryTypeSet* types, PropertyName* name,
                         types::HeapTypeSetKey* property);
    bool freezePropTypeSets(types::TemporaryTypeSet* types,
                            JSObject* foundProto, PropertyName* name);

    types::TemporaryTypeSet* bytecodeTypes(jsbytecode* pc);

    // Use one of the below methods for updating the current block, rather than
    // updating |current| directly. setCurrent() should only be used in cases
    // where the block cannot have phis whose type needs to be computed.

    bool setCurrentAndSpecializePhis(MBasicBlock* block) {
        if (block) {
            if (!block->specializePhis())
                return false;
        }
        setCurrent(block);
        return true;
    }

    void setCurrent(MBasicBlock* block) {
        current = block;
    }

    // A builder is inextricably tied to a particular script.
    JSScript* script_;

    // If off thread compilation is successful, the final code generator is
    // attached here. Code has been generated, but not linked (there is not yet
    // an IonScript). This is heap allocated, and must be explicitly destroyed,
    // performed by FinishOffThreadBuilder().
    CodeGenerator* backgroundCodegen_;

  public:
    void clearForBackEnd();

    JSScript* script() const { return script_; }

    CodeGenerator* backgroundCodegen() const { return backgroundCodegen_; }
    void setBackgroundCodegen(CodeGenerator* codegen) { backgroundCodegen_ = codegen; }

    AbortReason abortReason() { return abortReason_; }

    TypeDescrSetHash* getOrCreateDescrSetHash(); // fallible

    types::CompilerConstraintList* constraints() {
        return constraints_;
    }

    bool isInlineBuilder() const {
        return callerBuilder_ != nullptr;
    }

    const JSAtomState& names() { return compartment->runtime()->names(); }

  private:
    bool init();

    JSContext* analysisContext;
    BaselineFrameInspector* baselineFrame_;
    AbortReason abortReason_;
    TypeDescrSetHash* descrSetHash_;

    // Constraints for recording dependencies on type information.
    types::CompilerConstraintList* constraints_;

    // Basic analysis information about the script.
    BytecodeAnalysis analysis_;
    BytecodeAnalysis& analysis() {
        return analysis_;
    }

    types::TemporaryTypeSet* thisTypes, *argTypes, *typeArray;
    uint32_t typeArrayHint;
    uint32_t* bytecodeTypeMap;

    GSNCache gsn;
    ScopeCoordinateNameCache scopeCoordinateNameCache;

    jsbytecode* pc;
    MBasicBlock* current;
    uint32_t loopDepth_;

    /* Information used for inline-call builders. */
    MResumePoint* callerResumePoint_;
    jsbytecode* callerPC() {
        return callerResumePoint_ ? callerResumePoint_->pc() : nullptr;
    }
    IonBuilder* callerBuilder_;

    bool oom() {
        abortReason_ = AbortReason_Alloc;
        return false;
    }

    struct LoopHeader {
        jsbytecode* pc;
        MBasicBlock* header;

        LoopHeader(jsbytecode* pc, MBasicBlock* header)
          : pc(pc), header(header)
        {}
    };

    Vector<CFGState, 8, IonAllocPolicy> cfgStack_;
    Vector<ControlFlowInfo, 4, IonAllocPolicy> loops_;
    Vector<ControlFlowInfo, 0, IonAllocPolicy> switches_;
    Vector<ControlFlowInfo, 2, IonAllocPolicy> labels_;
    Vector<MInstruction*, 2, IonAllocPolicy> iterators_;
    Vector<LoopHeader, 0, IonAllocPolicy> loopHeaders_;
    BaselineInspector* inspector;

    size_t inliningDepth_;

    // Cutoff to disable compilation if excessive time is spent reanalyzing
    // loop bodies to compute a fixpoint of the types for loop variables.
    static const size_t MAX_LOOP_RESTARTS = 40;
    size_t numLoopRestarts_;

    // True if script->failedBoundsCheck is set for the current script or
    // an outer script.
    bool failedBoundsCheck_;

    // True if script->failedShapeGuard is set for the current script or
    // an outer script.
    bool failedShapeGuard_;

    // Has an iterator other than 'for in'.
    bool nonStringIteration_;

    // If this script can use a lazy arguments object, it will be pre-created
    // here.
    MInstruction* lazyArguments_;

    // If this is an inline builder, the call info for the builder.
    const CallInfo* inlineCallInfo_;
};

class CallInfo
{
    MDefinition* fun_;
    MDefinition* thisArg_;
    MDefinitionVector args_;

    bool constructing_;
    bool setter_;

  public:
    CallInfo(TempAllocator& alloc, bool constructing)
      : fun_(nullptr),
        thisArg_(nullptr),
        args_(alloc),
        constructing_(constructing),
        setter_(false)
    { }

    bool init(CallInfo& callInfo) {
        JS_ASSERT(constructing_ == callInfo.constructing());

        fun_ = callInfo.fun();
        thisArg_ = callInfo.thisArg();

        if (!args_.appendAll(callInfo.argv()))
            return false;

        return true;
    }

    bool init(MBasicBlock* current, uint32_t argc) {
        JS_ASSERT(args_.empty());

        // Get the arguments in the right order
        if (!args_.reserve(argc))
            return false;
        for (int32_t i = argc; i > 0; i--)
            args_.infallibleAppend(current->peek(-i));
        current->popn(argc);

        // Get |this| and |fun|
        setThis(current->pop());
        setFun(current->pop());

        return true;
    }

    void popFormals(MBasicBlock* current) {
        current->popn(numFormals());
    }

    void pushFormals(MBasicBlock* current) {
        current->push(fun());
        current->push(thisArg());

        for (uint32_t i = 0; i < argc(); i++)
            current->push(getArg(i));
    }

    uint32_t argc() const {
        return args_.length();
    }
    uint32_t numFormals() const {
        return argc() + 2;
    }

    void setArgs(MDefinitionVector* args) {
        JS_ASSERT(args_.empty());
        args_.appendAll(*args);
    }

    MDefinitionVector& argv() {
        return args_;
    }

    const MDefinitionVector& argv() const {
        return args_;
    }

    MDefinition* getArg(uint32_t i) const {
        JS_ASSERT(i < argc());
        return args_[i];
    }

    void setArg(uint32_t i, MDefinition* def) {
        JS_ASSERT(i < argc());
        args_[i] = def;
    }

    MDefinition* thisArg() const {
        JS_ASSERT(thisArg_);
        return thisArg_;
    }

    void setThis(MDefinition* thisArg) {
        thisArg_ = thisArg;
    }

    bool constructing() const {
        return constructing_;
    }

    bool isSetter() const {
        return setter_;
    }
    void markAsSetter() {
        setter_ = true;
    }

    MDefinition* fun() const {
        JS_ASSERT(fun_);
        return fun_;
    }

    void setFun(MDefinition* fun) {
        fun_ = fun;
    }

    void setImplicitlyUsedUnchecked() {
        fun_->setImplicitlyUsedUnchecked();
        thisArg_->setImplicitlyUsedUnchecked();
        for (uint32_t i = 0; i < argc(); i++)
            getArg(i)->setImplicitlyUsedUnchecked();
    }
};

bool TypeSetIncludes(types::TypeSet* types, MIRType input, types::TypeSet* inputTypes);

bool NeedsPostBarrier(CompileInfo& info, MDefinition* value);

} // namespace jit
} // namespace js

#endif // JS_ION

#endif /* jit_IonBuilder_h */