author | Ryan Pearl <rpearl@endofunctor.org> |
Fri, 29 Jun 2012 15:11:10 -0400 | |
changeset 106493 | 6688ede89a368ae3c56431db763d6ca9d14c6e9c |
parent 106492 | a1100d039be129994ed6b033f6b40d37f4da745a |
child 106494 | 5d3e8c9dc6f8bb0812175da55db94e1a6f588a98 |
push id | 23447 |
push user | danderson@mozilla.com |
push date | Tue, 11 Sep 2012 17:34:27 +0000 |
treeherder | mozilla-central@fdfaef738a00 [default view] [failures only] |
perfherder | [talos] [build metrics] [platform microbench] (compared to previous push) |
reviewers | dvander |
bugs | 699883 |
milestone | 16.0a1 |
first release with | nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
|
last release without | nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
|
--- a/js/src/Makefile.in +++ b/js/src/Makefile.in @@ -278,16 +278,17 @@ CPPSRCS += MIR.cpp \ MIRGraph.cpp \ MoveResolver.cpp \ EdgeCaseAnalysis.cpp \ Snapshots.cpp \ Safepoints.cpp \ TypeOracle.cpp \ TypePolicy.cpp \ ValueNumbering.cpp \ + RangeAnalysis.cpp \ VMFunctions.cpp \ AliasAnalysis.cpp \ $(NULL) endif #ENABLE_ION ifeq (86, $(findstring 86,$(TARGET_CPU))) CPPSRCS += CodeGenerator-x86-shared.cpp CPPSRCS += IonFrames-x86-shared.cpp CPPSRCS += MoveEmitter-x86-shared.cpp
--- a/js/src/ion/Ion.cpp +++ b/js/src/ion/Ion.cpp @@ -44,16 +44,17 @@ #include "IonBuilder.h" #include "IonSpewer.h" #include "LIR.h" #include "AliasAnalysis.h" #include "GreedyAllocator.h" #include "LICM.h" #include "ValueNumbering.h" #include "EdgeCaseAnalysis.h" +#include "RangeAnalysis.h" #include "LinearScan.h" #include "jscompartment.h" #include "IonCompartment.h" #include "CodeGenerator.h" #if defined(JS_CPU_X86) # include "x86/Lowering-x86.h" #elif defined(JS_CPU_X64) @@ -772,16 +773,34 @@ TestCompiler(IonBuilder &builder, MIRGra if (js_IonOptions.gvn) { ValueNumberer gvn(graph, js_IonOptions.gvnIsOptimistic); if (!gvn.analyze()) return false; IonSpewPass("GVN"); AssertGraphCoherency(graph); } + if (js_IonOptions.rangeAnalysis) { + RangeAnalysis r(graph); + if (!r.addBetaNobes()) + return false; + IonSpewPass("Beta"); + AssertGraphCoherency(graph); + + if (!r.analyze()) + return false; + IonSpewPass("Range Analysis"); + AssertGraphCoherency(graph); + + if (!r.removeBetaNobes()) + return false; + IonSpewPass("De-Beta"); + AssertGraphCoherency(graph); + } + if (!EliminateDeadCode(graph)) return false; IonSpewPass("DCE"); AssertGraphCoherency(graph); if (js_IonOptions.licm) { LICM licm(graph); if (!licm.analyze())
--- a/js/src/ion/Ion.h +++ b/js/src/ion/Ion.h @@ -91,16 +91,21 @@ struct IonOptions // Default: true bool inlining; // Toggles whether Edge Case Analysis is used. // // Default: true bool edgeCaseAnalysis; + // Toggles whether Range Analysis is used. + // + // Default: false + bool rangeAnalysis; + // How many invocations or loop iterations are needed before functions // are compiled. // // Default: 10,240 uint32 usesBeforeCompile; // How many invocations or loop iterations are needed before functions // are compiled when JM is disabled. @@ -148,16 +153,17 @@ struct IonOptions : gvn(true), gvnIsOptimistic(true), licm(true), osr(true), limitScriptSize(true), lsra(true), inlining(true), edgeCaseAnalysis(true), + rangeAnalysis(false), usesBeforeCompile(10240), usesBeforeCompileNoJaeger(40), usesBeforeInlining(usesBeforeCompile), maxStackArgs(4096), smallFunctionMaxBytecodeLength(100), smallFunctionUsesBeforeInlining(usesBeforeInlining / 4) { } };
--- a/js/src/ion/IonSpewer.cpp +++ b/js/src/ion/IonSpewer.cpp @@ -228,16 +228,18 @@ ion::CheckLogging() if (ContainsFlag(env, "aborts")) EnableChannel(IonSpew_Abort); if (ContainsFlag(env, "alias")) EnableChannel(IonSpew_Alias); if (ContainsFlag(env, "mir")) EnableChannel(IonSpew_MIR); if (ContainsFlag(env, "gvn")) EnableChannel(IonSpew_GVN); + if (ContainsFlag(env, "range")) + EnableChannel(IonSpew_Range); if (ContainsFlag(env, "licm")) EnableChannel(IonSpew_LICM); if (ContainsFlag(env, "regalloc")) EnableChannel(IonSpew_RegAlloc); if (ContainsFlag(env, "inline")) EnableChannel(IonSpew_Inlining); if (ContainsFlag(env, "snapshots")) EnableChannel(IonSpew_Snapshots);
--- a/js/src/ion/IonSpewer.h +++ b/js/src/ion/IonSpewer.h @@ -55,16 +55,18 @@ namespace ion { /* Used to abort SSA construction */ \ _(Abort) \ /* Information during MIR building */ \ _(MIR) \ /* Information during alias analysis */ \ _(Alias) \ /* Information during GVN */ \ _(GVN) \ + /* Information during Range analysis */ \ + _(Range) \ /* Information during LICM */ \ _(LICM) \ /* Information during LSRA */ \ _(RegAlloc) \ /* Information during inlining */ \ _(Inlining) \ /* Information during codegen */ \ _(Codegen) \
--- a/js/src/ion/Lowering.cpp +++ b/js/src/ion/Lowering.cpp @@ -463,17 +463,17 @@ LIRGenerator::visitCompare(MCompare *com } static void ReorderCommutative(MDefinition **lhsp, MDefinition **rhsp) { MDefinition *lhs = *lhsp; MDefinition *rhs = *rhsp; - // Put the constant in the left-hand side, if there is one. + // Put the constant in the right-hand side, if there is one. if (lhs->isConstant()) { *rhsp = lhs; *lhsp = rhs; } } bool LIRGenerator::lowerBitOp(JSOp op, MInstruction *ins) @@ -628,17 +628,17 @@ LIRGenerator::visitRound(MRound *ins) bool LIRGenerator::visitAbs(MAbs *ins) { MDefinition *num = ins->num(); if (num->type() == MIRType_Int32) { LAbsI *lir = new LAbsI(useRegisterAtStart(num)); // needed to handle abs(INT32_MIN) - if (!assignSnapshot(lir)) + if (!ins->range()->isFinite() && !assignSnapshot(lir)) return false; return defineReuseInput(lir, ins, 0); } else { JS_ASSERT(num->type() == MIRType_Double); LAbsD *lir = new LAbsD(useRegister(num)); return define(lir, ins); } } @@ -668,17 +668,17 @@ LIRGenerator::visitAdd(MAdd *ins) MDefinition *rhs = ins->getOperand(1); JS_ASSERT(lhs->type() == rhs->type()); if (ins->specialization() == MIRType_Int32) { JS_ASSERT(lhs->type() == MIRType_Int32); ReorderCommutative(&lhs, &rhs); LAddI *lir = new LAddI; - if (!ins->isTruncated() && !assignSnapshot(lir)) + if (ins->fallible() && !assignSnapshot(lir)) return false; return lowerForALU(lir, ins, lhs, rhs); } if (ins->specialization() == MIRType_Double) { JS_ASSERT(lhs->type() == MIRType_Double); return lowerForFPU(new LMathD(JSOP_ADD), ins, lhs, rhs); @@ -693,17 +693,17 @@ LIRGenerator::visitSub(MSub *ins) MDefinition *lhs = ins->lhs(); MDefinition *rhs = ins->rhs(); JS_ASSERT(lhs->type() == rhs->type()); if (ins->specialization() == MIRType_Int32) { JS_ASSERT(lhs->type() == MIRType_Int32); LSubI *lir = new LSubI; - if (!ins->isTruncated() && !assignSnapshot(lir)) + if (ins->fallible() && !assignSnapshot(lir)) return false; return lowerForALU(lir, ins, lhs, rhs); } if (ins->specialization() == MIRType_Double) { JS_ASSERT(lhs->type() == MIRType_Double); return lowerForFPU(new LMathD(JSOP_SUB), ins, lhs, rhs); } @@ -1220,16 +1220,19 @@ LIRGenerator::visitBoundsCheck(MBoundsCh useRegister(ins->length())); } return assignSnapshot(check) && add(check, ins); } bool LIRGenerator::visitBoundsCheckLower(MBoundsCheckLower *ins) { + if (!ins->fallible()) + return true; + LInstruction *check = new LBoundsCheckLower(useRegister(ins->index())); return assignSnapshot(check) && add(check, ins); } bool LIRGenerator::visitLoadElement(MLoadElement *ins) { JS_ASSERT(ins->elements()->type() == MIRType_Elements);
--- a/js/src/ion/MIR.cpp +++ b/js/src/ion/MIR.cpp @@ -293,16 +293,21 @@ MConstant::New(const Value &v) return new MConstant(v); } MConstant::MConstant(const js::Value &vp) : value_(vp) { setResultType(MIRTypeFromValue(vp)); setMovable(); + + if (type() == MIRType_Int32) { + range()->setLower(value().toInt32()); + range()->setUpper(value().toInt32()); + } } HashNumber MConstant::valueHash() const { // This disregards some state, since values are 64 bits. But for a hash, // it's completely acceptable. return (HashNumber)JSVAL_TO_IMPL(value_).asBits; @@ -1396,8 +1401,18 @@ MBoundsCheck::updateForReplacement(MDefi { return false; } setMinimum(newMinimum); setMaximum(newMaximum); return true; } + +void +MBeta::printOpcode(FILE *fp) +{ + PrintOpcodeName(fp, op()); + fprintf(fp, " "); + getOperand(0)->printName(fp); + fprintf(fp, " "); + comparison_.printRange(fp); +}
--- a/js/src/ion/MIR.h +++ b/js/src/ion/MIR.h @@ -40,30 +40,30 @@ * ***** END LICENSE BLOCK ***** */ #ifndef jsion_mir_h__ #define jsion_mir_h__ // This file declares everything needed to build actual MIR instructions: the // actual opcodes and instructions themselves, the instruction interface, and // use chains. - #include "jscntxt.h" #include "jslibmath.h" #include "jsinfer.h" #include "jsinferinlines.h" #include "TypeOracle.h" #include "TypePolicy.h" #include "IonAllocPolicy.h" #include "InlineList.h" #include "MOpcodes.h" #include "FixedArityList.h" #include "IonMacroAssembler.h" #include "Bailouts.h" #include "FixedList.h" +#include "RangeAnalysis.h" #include "CompilerRoot.h" namespace js { namespace ion { class ValueNumberData; static const inline MIRType MIRTypeFromValue(const js::Value &vp) { @@ -254,16 +254,21 @@ class MDefinition : public MNode Op_Invalid }; private: InlineForwardList<MUse> uses_; // Use chain. uint32 id_; // Instruction ID, which after block re-ordering // is sorted within a basic block. ValueNumberData *valueNumber_; // The instruction's value number (see GVN for details in use) + + // Bug 765126: This should be a pointer. The range should only be allocated if range analysis is + // enabled. + Range range_; // The most specific known range for this def. + MIRType resultType_; // Representation of result type. uint32 flags_; // Bit flags. union { MDefinition *dependency_; // Implicit dependency (store, call, etc.) of this instruction. // Used by alias analysis, GVN and LICM. uint32 virtualRegister_; // Used by lowering to map definitions to virtual registers. }; @@ -304,39 +309,49 @@ class MDefinition : public MNode return trackedPc_; } #endif public: MDefinition() : id_(0), valueNumber_(NULL), + range_(), resultType_(MIRType_None), flags_(0), dependency_(NULL) #ifdef TRACK_SNAPSHOTS , trackedPc_(NULL) #endif { } virtual Opcode op() const = 0; void printName(FILE *fp); static void PrintOpcodeName(FILE *fp, Opcode op); virtual void printOpcode(FILE *fp); + Range *range() { + return &range_; + } + virtual HashNumber valueHash() const; virtual bool congruentTo(MDefinition* const &ins) const { return false; } bool congruentIfOperandsEqual(MDefinition * const &ins) const; virtual MDefinition *foldsTo(bool useValueNumbers); virtual void analyzeEdgeCasesForward(); virtual void analyzeEdgeCasesBackward(); virtual void analyzeTruncateBackward(); + // Propagate a range. Return true if the range changed. + virtual bool recomputeRange() { + return false; + } + MNode::Kind kind() const { return MNode::Definition; } uint32 id() const { JS_ASSERT(block_); return id_; } @@ -1648,16 +1663,17 @@ class MToInt32 : public MUnaryInstructio bool canBeNegativeZero_; MToInt32(MDefinition *def) : MUnaryInstruction(def), canBeNegativeZero_(true) { setResultType(MIRType_Int32); setMovable(); + range()->set(JSVAL_INT_MIN, JSVAL_INT_MAX); } public: INSTRUCTION_HEADER(ToInt32); static MToInt32 *New(MDefinition *def) { return new MToInt32(def); } @@ -1688,16 +1704,17 @@ class MToInt32 : public MUnaryInstructio // operations. This is an infallible ValueToECMAInt32. class MTruncateToInt32 : public MUnaryInstruction { MTruncateToInt32(MDefinition *def) : MUnaryInstruction(def) { setResultType(MIRType_Int32); setMovable(); + range()->set(JSVAL_INT_MIN, JSVAL_INT_MAX); } public: INSTRUCTION_HEADER(TruncateToInt32); static MTruncateToInt32 *New(MDefinition *def) { return new MTruncateToInt32(def); } @@ -1753,16 +1770,17 @@ class MBitNot public BitwisePolicy { protected: MBitNot(MDefinition *input) : MUnaryInstruction(input) { setResultType(MIRType_Int32); setMovable(); + range()->set(JSVAL_INT_MIN, JSVAL_INT_MAX); } public: INSTRUCTION_HEADER(BitNot); static MBitNot *New(MDefinition *input); TypePolicy *typePolicy() { return this; @@ -1847,16 +1865,17 @@ class MBinaryBitwiseInstruction public BitwisePolicy { protected: MBinaryBitwiseInstruction(MDefinition *left, MDefinition *right) : MBinaryInstruction(left, right) { setResultType(MIRType_Int32); setMovable(); + range()->set(JSVAL_INT_MIN, JSVAL_INT_MAX); } public: TypePolicy *typePolicy() { return this; } MDefinition *foldsTo(bool useValueNumbers); @@ -1960,16 +1979,26 @@ class MLsh : public MShiftInstruction INSTRUCTION_HEADER(Lsh); static MLsh *New(MDefinition *left, MDefinition *right); MDefinition *foldIfZero(size_t operand) { // 0 << x => 0 // x << 0 => x return getOperand(0); } + + bool recomputeRange() { + MDefinition *right = getOperand(1); + if (!right->isConstant()) + return false; + + int32 c = right->toConstant()->value().toInt32(); + const Range *other = getOperand(0)->range(); + return range()->update(Range::shl(other, c)); + } }; class MRsh : public MShiftInstruction { MRsh(MDefinition *left, MDefinition *right) : MShiftInstruction(left, right) { } @@ -1977,16 +2006,25 @@ class MRsh : public MShiftInstruction INSTRUCTION_HEADER(Rsh); static MRsh *New(MDefinition *left, MDefinition *right); MDefinition *foldIfZero(size_t operand) { // 0 >> x => 0 // x >> 0 => x return getOperand(0); } + bool recomputeRange() { + MDefinition *right = getOperand(1); + if (!right->isConstant()) + return false; + + int32 c = right->toConstant()->value().toInt32(); + Range *other = getOperand(0)->range(); + return range()->update(Range::shr(other, c)); + } }; class MUrsh : public MShiftInstruction { bool canOverflow_; MUrsh(MDefinition *left, MDefinition *right) : MShiftInstruction(left, right), @@ -2091,16 +2129,27 @@ class MAbs } bool congruentTo(MDefinition *const &ins) const { return congruentIfOperandsEqual(ins); } AliasSet getAliasSet() const { return AliasSet::None(); } + bool recomputeRange() { + if (specialization_ != MIRType_Int32) + return false; + + Range *other = getOperand(0)->range(); + Range r(0, + Max(Range::abs64((int64_t)other->lower()), + Range::abs64((int64_t)other->upper()))); + + return range()->update(r); + } }; class MSqrt : public MUnaryInstruction, public DoublePolicy<0> { MSqrt(MDefinition *num) : MUnaryInstruction(num) @@ -2200,16 +2249,28 @@ class MAdd : public MBinaryArithInstruct } void setTruncated(bool val) { implicitTruncate_ = val; } bool updateForReplacement(MDefinition *ins); double getIdentity() { return 0; } + + bool fallible() { + return !isTruncated() && !range()->isFinite(); + } + + bool recomputeRange() { + if (specialization() != MIRType_Int32) + return false; + Range *left = getOperand(0)->range(); + Range *right = getOperand(1)->range(); + return range()->update(Range::add(left, right)); + } }; class MSub : public MBinaryArithInstruction { bool implicitTruncate_; MSub(MDefinition *left, MDefinition *right) : MBinaryArithInstruction(left, right), implicitTruncate_(false) @@ -2230,26 +2291,36 @@ class MSub : public MBinaryArithInstruct void setTruncated(bool val) { implicitTruncate_ = val; } bool updateForReplacement(MDefinition *ins); double getIdentity() { return 0; } + + bool fallible() { + return !isTruncated() && !range()->isFinite(); + } + + bool recomputeRange() { + if (specialization() != MIRType_Int32) + return false; + Range *left = getOperand(0)->range(); + Range *right = getOperand(1)->range(); + return range()->update(Range::sub(left, right)); + } }; class MMul : public MBinaryArithInstruction { - bool canOverflow_; bool canBeNegativeZero_; MMul(MDefinition *left, MDefinition *right) : MBinaryArithInstruction(left, right), - canOverflow_(true), canBeNegativeZero_(true) { setResultType(MIRType_Value); } public: INSTRUCTION_HEADER(Mul); static MMul *New(MDefinition *left, MDefinition *right) { @@ -2260,26 +2331,36 @@ class MMul : public MBinaryArithInstruct void analyzeEdgeCasesForward(); void analyzeEdgeCasesBackward(); double getIdentity() { return 1; } bool canOverflow() { - return canOverflow_; + return !range()->isFinite(); } bool canBeNegativeZero() { + if (range()->lower() >= 0 && range()->upper() >= 0) + return false; return canBeNegativeZero_; } bool updateForReplacement(MDefinition *ins); bool fallible() { - return canBeNegativeZero_ || canOverflow_; + return canBeNegativeZero_ || canOverflow(); + } + + bool recomputeRange() { + if (specialization() != MIRType_Int32) + return false; + Range *left = getOperand(0)->range(); + Range *right = getOperand(1)->range(); + return range()->update(Range::mul(left, right)); } }; class MDiv : public MBinaryArithInstruction { bool canBeNegativeZero_; bool canBeNegativeOverflow_; bool canBeDivideByZero_; @@ -2347,16 +2428,27 @@ class MMod : public MBinaryArithInstruct return new MMod(left, right); } MDefinition *foldsTo(bool useValueNumbers); double getIdentity() { JS_NOT_REACHED("not used"); return 1; } + + bool recomputeRange() { + if (specialization() != MIRType_Int32) + return false; + Range *other = getOperand(0)->range(); + int64_t a = Range::abs64((int64_t)other->lower()); + int64_t b = Range::abs64((int64_t)other->upper()); + Range r(Min(-a+1, -b+1), + Max( a-1, b-1)); + return range()->update(r); + } }; class MConcat : public MBinaryInstruction, public BinaryStringPolicy { MConcat(MDefinition *left, MDefinition *right) : MBinaryInstruction(left, right) @@ -2386,16 +2478,18 @@ class MCharCodeAt : public MBinaryInstruction, public MixPolicy<StringPolicy, IntPolicy<1> > { MCharCodeAt(MDefinition *str, MDefinition *index) : MBinaryInstruction(str, index) { setMovable(); setResultType(MIRType_Int32); + range()->set(0, 65535); //ECMA 262 says that the integer will be + //non-negative and less than 65535. } public: INSTRUCTION_HEADER(CharCodeAt); static MCharCodeAt *New(MDefinition *str, MDefinition *index) { return new MCharCodeAt(str, index); } @@ -2492,16 +2586,61 @@ class MPhi : public MDefinition, public } void setIterator() { isIterator_ = true; } AliasSet getAliasSet() const { return AliasSet::None(); } + + bool recomputeRange() { + if (type() != MIRType_Int32) + return false; + + Range r; + r.update(getOperand(0)->range()); + + for (size_t i = 0; i < numOperands(); i++) + r.unionWith(getOperand(i)->range()); + + return range()->update(&r); + } +}; + +// The goal of a Beta node is to split a def at a conditionally taken +// branch, so that uses dominated by it have a different name. +class MBeta : public MUnaryInstruction +{ + private: + Range comparison_; + MDefinition *val_; + MBeta(MDefinition *val, int32 low, int32 high) + : MUnaryInstruction(val), + comparison_(low, high), + val_(val) + { + } + + public: + INSTRUCTION_HEADER(Beta); + void printOpcode(FILE *fp); + static MBeta *New(MDefinition *val, int32 low, int32 high) + { + return new MBeta(val, low, high); + } + + AliasSet getAliasSet() const { + return AliasSet::None(); + } + + bool recomputeRange() { + return range()->update( + Range::intersect(val_->range(), &comparison_)); + } }; // MIR representation of a Value on the OSR StackFrame. // The Value is indexed off of OsrFrameReg. class MOsrValue : public MUnaryInstruction { private: ptrdiff_t frameOffset_; @@ -3063,16 +3202,19 @@ class MBoundsCheckLower return minimum_; } void setMinimum(int32 n) { minimum_ = n; } AliasSet getAliasSet() const { return AliasSet::None(); } + bool fallible() { + return range()->lower() < minimum_; + } }; // Load a value from a dense array's element vector and does a hole check if the // array is not known to be packed. class MLoadElement : public MBinaryInstruction, public SingleObjectPolicy { @@ -3506,16 +3648,17 @@ class MClampToUint8 : public MUnaryInstruction, public ClampPolicy { MClampToUint8(MDefinition *input) : MUnaryInstruction(input) { setResultType(MIRType_Int32); setMovable(); + range()->set(0, 255); } public: INSTRUCTION_HEADER(ClampToUint8); static MClampToUint8 *New(MDefinition *input) { return new MClampToUint8(input); }
--- a/js/src/ion/MOpcodes.h +++ b/js/src/ion/MOpcodes.h @@ -50,16 +50,17 @@ namespace ion { _(Constant) \ _(Parameter) \ _(Callee) \ _(TableSwitch) \ _(Goto) \ _(Test) \ _(Compare) \ _(Phi) \ + _(Beta) \ _(OsrValue) \ _(OsrScopeChain) \ _(ReturnFromCtor) \ _(CheckOverRecursed) \ _(RecompileCheck) \ _(DefVar) \ _(CreateThis) \ _(PrepareCall) \
new file mode 100644 --- /dev/null +++ b/js/src/ion/RangeAnalysis.cpp @@ -0,0 +1,427 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* vim: set ts=4 sw=4 et tw=79: */ +/* 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/. */ + +#include <stdio.h> + +#include "Ion.h" +#include "MIR.h" +#include "MIRGraph.h" +#include "RangeAnalysis.h" +#include "IonSpewer.h" + +using namespace js; +using namespace js::ion; + +// This algorithm is based on the paper "Eliminating Range Checks Using +// Static Single Assignment Form" by Gough and Klaren. +// +// We associate a range object with each SSA name, and the ranges are consulted +// in order to determine whether overflow is possible for arithmetic +// computations. +// +// An important source of range information that requires care to take +// advantage of is conditional control flow. Consider the code below: +// +// if (x < 0) { +// y = x + 2000000000; +// } else { +// if (x < 1000000000) { +// y = x * 2; +// } else { +// y = x - 3000000000; +// } +// } +// +// The arithmetic operations in this code cannot overflow, but it is not +// sufficient to simply associate each name with a range, since the information +// differs between basic blocks. The traditional dataflow approach would be +// associate ranges with (name, basic block) pairs. This solution is not +// satisfying, since we lose the benefit of SSA form: in SSA form, each +// definition has a unique name, so there is no need to track information about +// the control flow of the program. +// +// The approach used here is to add a new form of pseudo operation called a +// beta node, which associates range information with a value. These beta +// instructions take one argument and additionally have an auxiliary constant +// range associated with them. Operationally, beta nodes are just copies, but +// the invariant expressed by beta node copies is that the output will fall +// inside the range given by the beta node. Gough and Klaeren refer to SSA +// extended with these beta nodes as XSA form. The following shows the example +// code transformed into XSA form: +// +// if (x < 0) { +// x1 = Beta(x, [INT_MIN, -1]); +// y1 = x1 + 2000000000; +// } else { +// x2 = Beta(x, [0, INT_MAX]); +// if (x2 < 1000000000) { +// x3 = Beta(x2, [INT_MIN, 999999999]); +// y2 = x3*2; +// } else { +// x4 = Beta(x2, [1000000000, INT_MAX]); +// y3 = x4 - 3000000000; +// } +// y4 = Phi(y2, y3); +// } +// y = Phi(y1, y4); +// +// We insert beta nodes for the purposes of range analysis (they might also be +// usefully used for other forms of bounds check elimination) and remove them +// after range analysis is performed. The remaining compiler phases do not ever +// encounter beta nodes. + +RangeAnalysis::RangeAnalysis(MIRGraph &graph) + : graph_(graph) +{ +} + +static bool +IsDominatedUse(MBasicBlock *block, MUse *use) +{ + MNode *n = use->node(); + bool isPhi = n->isDefinition() && n->toDefinition()->isPhi(); + + if (isPhi) + return block->dominates(n->block()->getPredecessor(use->index())); + + return block->dominates(n->block()); +} + +static inline void +SpewRange(MDefinition *def) +{ +#ifdef DEBUG + if (IonSpewEnabled(IonSpew_Range)) { + IonSpewHeader(IonSpew_Range); + fprintf(IonSpewFile, "%d has range ", def->id()); + def->range()->printRange(IonSpewFile); + fprintf(IonSpewFile, "\n"); + } +#endif +} + +void +RangeAnalysis::replaceDominatedUsesWith(MDefinition *orig, MDefinition *dom, + MBasicBlock *block) +{ + for (MUseIterator i(orig->usesBegin()); i != orig->usesEnd(); ) { + if (i->node() != dom && IsDominatedUse(block, *i)) + i = i->node()->replaceOperand(i, dom); + else + i++; + } +} + +bool +RangeAnalysis::addBetaNobes() +{ + IonSpew(IonSpew_Range, "Adding beta nobes"); + + for (PostorderIterator i(graph_.poBegin()); i != graph_.poEnd(); i++) { + MBasicBlock *block = *i; + IonSpew(IonSpew_Range, "Looking at block %d", block->id()); + + BranchDirection branch_dir; + MTest *test = block->immediateDominatorBranch(&branch_dir); + + if (!test || !test->getOperand(0)->isCompare()) + continue; + + MCompare *compare = test->getOperand(0)->toCompare(); + + MDefinition *left = compare->getOperand(0); + MDefinition *right = compare->getOperand(1); + int32 bound; + MDefinition *val = NULL; + + JSOp jsop = compare->jsop(); + + if (branch_dir == FALSE_BRANCH) + jsop = analyze::NegateCompareOp(jsop); + + if (left->isConstant() && left->toConstant()->value().isInt32()) { + bound = left->toConstant()->value().toInt32(); + val = right; + jsop = analyze::ReverseCompareOp(jsop); + } else if (right->isConstant() && right->toConstant()->value().isInt32()) { + bound = right->toConstant()->value().toInt32(); + val = left; + } else { + MDefinition *smaller = NULL; + MDefinition *greater = NULL; + if (jsop == JSOP_LT) { + smaller = left; + greater = right; + } else if (JSOP_GT) { + smaller = right; + greater = left; + } + if (smaller && greater) { + MBeta *beta; + beta = MBeta::New(smaller, JSVAL_INT_MIN, JSVAL_INT_MAX-1); + block->insertBefore(*block->begin(), beta); + replaceDominatedUsesWith(smaller, beta, block); + beta = MBeta::New(greater, JSVAL_INT_MIN+1, JSVAL_INT_MAX); + block->insertBefore(*block->begin(), beta); + replaceDominatedUsesWith(greater, beta, block); + } + continue; + } + + JS_ASSERT(val); + + + int32 low = JSVAL_INT_MIN; + int32 high = JSVAL_INT_MAX; + switch (jsop) { + case JSOP_LE: + high = bound; + break; + case JSOP_LT: + if (!SafeSub(bound, 1, &bound)) + break; + high = bound; + break; + case JSOP_GE: + low = bound; + break; + case JSOP_GT: + if (!SafeAdd(bound, 1, &bound)) + break; + low = bound; + break; + case JSOP_EQ: + low = bound; + high = bound; + default: + break; // well, for neq we could have + // [-\inf, bound-1] U [bound+1, \inf] but we only use contiguous ranges. + } + + IonSpew(IonSpew_Range, "Adding beta node for %d", val->id()); + MBeta *beta = MBeta::New(val, low, high); + block->insertBefore(*block->begin(), beta); + replaceDominatedUsesWith(val, beta, block); + } + + return true; +} + +bool +RangeAnalysis::removeBetaNobes() +{ + IonSpew(IonSpew_Range, "Removing beta nobes"); + + for (PostorderIterator i(graph_.poBegin()); i != graph_.poEnd(); i++) { + MBasicBlock *block = *i; + for (MDefinitionIterator iter(*i); iter; ) { + MDefinition *def = *iter; + if (def->isBeta()) { + MDefinition *op = def->getOperand(0); + IonSpew(IonSpew_Range, "Removing beta node %d for %d", + def->id(), op->id()); + def->replaceAllUsesWith(op); + iter = block->discardDefAt(iter); + } else { + // We only place Beta nodes at the beginning of basic + // blocks, so if we see something else, we can move on + // to the next block. + break; + } + } + } + return true; +} + +void +Range::printRange(FILE *fp) +{ + JS_ASSERT_IF(lower_infinite_, lower_ == JSVAL_INT_MIN); + JS_ASSERT_IF(upper_infinite_, upper_ == JSVAL_INT_MAX); + fprintf(fp, "["); + if (lower_infinite_) { fprintf(fp, "-inf"); } else { fprintf(fp, "%d", lower_); } + fprintf(fp, ", "); + if (upper_infinite_) { fprintf(fp, "inf"); } else { fprintf(fp, "%d", upper_); } + fprintf(fp, "]"); +} + +Range +Range::intersect(const Range *lhs, const Range *rhs) +{ + Range r( + Max(lhs->lower_, rhs->lower_), + Min(lhs->upper_, rhs->upper_)); + + r.lower_infinite_ = lhs->lower_infinite_ && rhs->lower_infinite_; + r.upper_infinite_ = lhs->upper_infinite_ && rhs->upper_infinite_; + + // :TODO: This information could be used better. If upper < lower, then we + // have conflicting constraints. Consider: + // + // if (x < 0) { + // if (x > 0) { + // [Some code.] + // } + // } + // + // In this case, the block is dead. Right now, we just disregard this fact + // and make the range infinite, rather than empty. + // + // Instead, we should use it to eliminate the dead block. + // (Bug 765127) + if (r.upper_ < r.lower_) + r.makeRangeInfinite(); + return r; +} + +void +Range::unionWith(const Range *other) +{ + setLower(Min(lower_, other->lower_)); + setUpper(Max(upper_, other->upper_)); + lower_infinite_ |= other->lower_infinite_; + upper_infinite_ |= other->upper_infinite_; +} + +Range +Range::add(const Range *lhs, const Range *rhs) +{ + return Range( + (int64_t)lhs->lower_ + (int64_t)rhs->lower_, + (int64_t)lhs->upper_ + (int64_t)rhs->upper_); +} + +Range +Range::sub(const Range *lhs, const Range *rhs) +{ + return Range( + (int64_t)lhs->lower_ - (int64_t)rhs->upper_, + (int64_t)lhs->upper_ - (int64_t)rhs->lower_); +} + +Range +Range::mul(const Range *lhs, const Range *rhs) +{ + int64_t a = (int64_t)lhs->lower_ * (int64_t)rhs->lower_; + int64_t b = (int64_t)lhs->lower_ * (int64_t)rhs->upper_; + int64_t c = (int64_t)lhs->upper_ * (int64_t)rhs->lower_; + int64_t d = (int64_t)lhs->upper_ * (int64_t)rhs->upper_; + return Range( + Min( Min(a, b), Min(c, d) ), + Max( Max(a, b), Max(c, d) )); +} + +Range +Range::shl(const Range *lhs, int32 c) +{ + int32 shift = c & 0x1f; + return Range( + (int64_t)lhs->lower_ << shift, + (int64_t)lhs->upper_ << shift); +} + +Range +Range::shr(const Range *lhs, int32 c) +{ + int32 shift = c & 0x1f; + return Range( + (int64_t)lhs->lower_ >> shift, + (int64_t)lhs->upper_ >> shift); +} + +bool +Range::update(const Range *other) +{ + bool changed = + lower_ != other->lower_ || + lower_infinite_ != other->lower_infinite_ || + upper_ != other->upper_ || + upper_infinite_ != other->upper_infinite_; + + if (changed) { + lower_ = other->lower_; + lower_infinite_ = other->lower_infinite_; + upper_ = other->upper_; + upper_infinite_ = other->upper_infinite_; + } + + return changed; +} + +static inline bool +AddToWorklist(MDefinitionVector &worklist, MDefinition *def) +{ + if (def->isInWorklist()) + return true; + def->setInWorklist(); + return worklist.append(def); +} + +static inline MDefinition * +PopFromWorklist(MDefinitionVector &worklist) +{ + JS_ASSERT(!worklist.empty()); + MDefinition *def = worklist.popCopy(); + def->setNotInWorklist(); + return def; +} + + +bool +RangeAnalysis::analyze() +{ + IonSpew(IonSpew_Range, "Doing range propagation"); + MDefinitionVector worklist; + + for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) { + for (MDefinitionIterator iter(*block); iter; iter++) { + MDefinition *def = *iter; + + if (!def->isPhi() && !def->isBeta()) + continue; + AddToWorklist(worklist, def); + + } + } + size_t iters = 0; +#define MAX_ITERS 4096 + // XXX: hack: range analysis iloops on jit-test/tests/basic/fannkuch.js + // To circumvent this and land the pass, we just run for a fixed number of + // iterations. + // + // (Bug 765119) + while (!worklist.empty() /* && iters < MAX_ITERS*/) { + MDefinition *def = PopFromWorklist(worklist); + IonSpew(IonSpew_Range, "recomputing range on %d", def->id()); + SpewRange(def); + if (def->recomputeRange()) { + JS_ASSERT(def->range()->lower() <= def->range()->upper()); + IonSpew(IonSpew_Range, "Range changed; adding consumers"); + for (MUseDefIterator use(def); use; use++) { + if(!AddToWorklist(worklist, use.def())) + return false; + } + } + iters++; + } + // Cleanup (in case we stopped due to MAX_ITERS) + for(size_t i = 0; i < worklist.length(); i++) + worklist[i]->setNotInWorklist(); + +#undef MAX_ITERS + +#ifdef DEBUG + for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) { + for (MDefinitionIterator iter(*block); iter; iter++) { + MDefinition *def = *iter; + SpewRange(def); + JS_ASSERT(def->range()->lower() <= def->range()->upper()); + JS_ASSERT(!def->isInWorklist()); + } + } +#endif + return true; +}
new file mode 100644 --- /dev/null +++ b/js/src/ion/RangeAnalysis.h @@ -0,0 +1,209 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=4 sw=4 et tw=79: + * + * ***** BEGIN LICENSE BLOCK ***** + * Version: MPL 1.1/GPL 2.0/LGPL 2.1 + * + * The contents of this file are subject to the Mozilla Public License Version + * 1.1 (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * Software distributed under the License is distributed on an "AS IS" basis, + * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License + * for the specific language governing rights and limitations under the + * License. + * + * The Original Code is Mozilla Communicator client code, released + * March 31, 1998. + * + * The Initial Developer of the Original Code is + * Netscape Communications Corporation. + * Portions created by the Initial Developer are Copyright (C) 1998 + * the Initial Developer. All Rights Reserved. + * + * Contributor(s): + * Ryan Pearl <rpearl@endofunctor.org> + * Michael Sullivan <sully@msully.net> + * + * Alternatively, the contents of this file may be used under the terms of + * either of the GNU General Public License Version 2 or later (the "GPL"), + * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), + * in which case the provisions of the GPL or the LGPL are applicable instead + * of those above. If you wish to allow use of your version of this file only + * under the terms of either the GPL or the LGPL, and not to allow others to + * use your version of this file under the terms of the MPL, indicate your + * decision by deleting the provisions above and replace them with the notice + * and other provisions required by the GPL or the LGPL. If you do not delete + * the provisions above, a recipient may use your version of this file under + * the terms of any one of the MPL, the GPL or the LGPL. + * + * ***** END LICENSE BLOCK ***** */ + +#ifndef jsion_range_analysis_h__ +#define jsion_range_analysis_h__ + +#include "wtf/Platform.h" +#include "MIR.h" +#include "CompileInfo.h" + +namespace js { +namespace ion { + +class MBasicBlock; +class MIRGraph; + +class RangeAnalysis +{ + protected: + bool blockDominates(MBasicBlock *b, MBasicBlock *b2); + void replaceDominatedUsesWith(MDefinition *orig, MDefinition *dom, + MBasicBlock *block); + + protected: + MIRGraph &graph_; + + public: + RangeAnalysis(MIRGraph &graph); + bool addBetaNobes(); + bool analyze(); + bool removeBetaNobes(); +}; + +class Range { + private: + // :TODO: we should do symbolic range evaluation, where we have + // information of the form v1 < v2 for arbitrary defs v1 and v2, not + // just constants of type int32. + // (Bug 766592) + + // We represent ranges where the endpoints can be in the set: + // {-infty} U [INT_MIN, INT_MAX] U {infty}. A bound of +/- + // infty means that the value may have overflowed in that + // direction. When computing the range of an integer + // instruction, the ranges of the operands can be clamped to + // [INT_MIN, INT_MAX], since if they had overflowed they would + // no longer be integers. This is important for optimizations + // and somewhat subtle. + // + // N.B.: All of the operations that compute new ranges based + // on existing ranges will ignore the _infinite_ flags of the + // input ranges; that is, they implicitly clamp the ranges of + // the inputs to [INT_MIN, INT_MAX]. Therefore, while our range might + // be infinite (and could overflow), when using this information to + // propagate through other ranges, we disregard this fact; if that code + // executes, then the overflow did not occur, so we may safely assume + // that the range is [INT_MIN, INT_MAX] instead. + // + // To facilitate this trick, we maintain the invariants that: + // 1) lower_infinite == true implies lower_ == JSVAL_INT_MIN + // 2) upper_infinite == true implies upper_ == JSVAL_INT_MAX + int32 lower_; + bool lower_infinite_; + int32 upper_; + bool upper_infinite_; + + public: + Range() : + lower_(JSVAL_INT_MIN), + lower_infinite_(true), + upper_(JSVAL_INT_MAX), + upper_infinite_(true) + {} + + Range(int64_t l, int64_t h) { + setLower(l); + setUpper(h); + } + + static int64_t abs64(int64_t x) { +#ifdef WTF_OS_WINDOWS + return _abs64(x); +#else + return llabs(x); +#endif + } + + void printRange(FILE *fp); + bool update(const Range *other); + bool update(const Range &other) { + return update(&other); + } + + // Unlike the other operations, unionWith is an in-place + // modification. This is to avoid a bunch of useless extra + // copying when chaining together unions when handling Phi + // nodes. + void unionWith(const Range *other); + + static Range intersect(const Range *lhs, const Range *rhs); + static Range add(const Range *lhs, const Range *rhs); + static Range sub(const Range *lhs, const Range *rhs); + static Range mul(const Range *lhs, const Range *rhs); + + static Range shl(const Range *lhs, int32 c); + static Range shr(const Range *lhs, int32 c); + + inline void makeLowerInfinite() { + lower_infinite_ = true; + lower_ = JSVAL_INT_MIN; + } + inline void makeUpperInfinite() { + upper_infinite_ = true; + upper_ = JSVAL_INT_MAX; + } + inline void makeRangeInfinite() { + makeLowerInfinite(); + makeUpperInfinite(); + } + + inline bool isLowerInfinite() const { + return lower_infinite_; + } + inline bool isUpperInfinite() const { + return upper_infinite_; + } + + inline bool isFinite() const { + return !isLowerInfinite() && !isUpperInfinite(); + } + + inline int32 lower() const { + return lower_; + } + + inline int32 upper() const { + return upper_; + } + + inline void setLower(int64_t x) { + if (x > JSVAL_INT_MAX) { // c.c + lower_ = JSVAL_INT_MAX; + } else if (x < JSVAL_INT_MIN) { + makeLowerInfinite(); + } else { + lower_ = (int32)x; + lower_infinite_ = false; + } + } + inline void setUpper(int64_t x) { + if (x > JSVAL_INT_MAX) { + makeUpperInfinite(); + } else if (x < JSVAL_INT_MIN) { // c.c + upper_ = JSVAL_INT_MIN; + } else { + upper_ = (int32)x; + upper_infinite_ = false; + } + } + void set(int64_t l, int64_t h) { + setLower(l); + setUpper(h); + } +}; + +} // namespace ion +} // namespace js + +#endif // jsion_range_analysis_h__ +
--- a/js/src/shell/js.cpp +++ b/js/src/shell/js.cpp @@ -4715,16 +4715,25 @@ ProcessArgs(JSContext *cx, JSObject *obj if (strcmp(str, "on") == 0) ion::js_IonOptions.edgeCaseAnalysis = true; else if (strcmp(str, "off") == 0) ion::js_IonOptions.edgeCaseAnalysis = false; else return OptionFailure("ion-edgecase-analysis", str); } + if (const char *str = op->getStringOption("ion-range-analysis")) { + if (strcmp(str, "on") == 0) + ion::js_IonOptions.rangeAnalysis = true; + else if (strcmp(str, "off") == 0) + ion::js_IonOptions.rangeAnalysis = false; + else + return OptionFailure("ion-range-analysis", str); + } + if (const char *str = op->getStringOption("ion-inlining")) { if (strcmp(str, "on") == 0) ion::js_IonOptions.inlining = true; else if (strcmp(str, "off") == 0) ion::js_IonOptions.inlining = false; else return OptionFailure("ion-inlining", str); } @@ -4968,16 +4977,18 @@ main(int argc, char **argv, char **envp) "Specify Ion global value numbering:\n" " off: disable GVN\n" " pessimistic: (default) use pessimistic GVN\n" " optimistic: use optimistic GVN") || !op.addStringOption('\0', "ion-licm", "on/off", "Loop invariant code motion (default: on, off to disable)") || !op.addStringOption('\0', "ion-edgecase-analysis", "on/off", "Find edge cases where Ion can avoid bailouts (default: on, off to disable)") + || !op.addStringOption('\0', "ion-range-analysis", "on/off", + "Range analysis (default: off, on to enable)") || !op.addStringOption('\0', "ion-inlining", "on/off", "Inline methods where possible (default: on, off to disable)") || !op.addStringOption('\0', "ion-osr", "on/off", "On-Stack Replacement (default: on, off to disable)") || !op.addStringOption('\0', "ion-limit-script-size", "on/off", "Don't compile very large scripts (default: on, off to disable)") || !op.addStringOption('\0', "ion-regalloc", "[mode]", "Specify Ion register allocation:\n"