author | Ryan VanderMeulen <ryanvm@gmail.com> |
Fri, 23 Nov 2012 10:04:14 -0500 | |
changeset 114072 | 5493ee135368050c2a80ff4a262a0b1f0aebaf65 |
parent 114071 | 0a197ef0840cae2f5f493b56362a1ce7af859605 |
child 114073 | 85c1a0de5374a3a60526275d09baaf2d6861f89a |
push id | 23901 |
push user | ryanvm@gmail.com |
push date | Fri, 23 Nov 2012 21:11:03 +0000 |
treeherder | mozilla-central@0d373cf880fd [default view] [failures only] |
perfherder | [talos] [build metrics] [platform microbench] (compared to previous push) |
bugs | 766592 |
milestone | 20.0a1 |
backs out | 0a197ef0840cae2f5f493b56362a1ce7af859605 |
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/ion/Ion.cpp +++ b/js/src/ion/Ion.cpp @@ -863,27 +863,16 @@ CompileBackEnd(MIRGenerator *mir) return NULL; IonSpewPass("GVN"); AssertGraphCoherency(graph); if (mir->shouldCancel("GVN")) return NULL; } - if (js_IonOptions.licm) { - LICM licm(mir, graph); - if (!licm.analyze()) - return NULL; - IonSpewPass("LICM"); - AssertGraphCoherency(graph); - - if (mir->shouldCancel("LICM")) - return NULL; - } - if (js_IonOptions.rangeAnalysis) { RangeAnalysis r(graph); if (!r.addBetaNobes()) return NULL; IonSpewPass("Beta"); AssertGraphCoherency(graph); if (mir->shouldCancel("RA Beta")) @@ -909,16 +898,27 @@ CompileBackEnd(MIRGenerator *mir) if (!EliminateDeadCode(mir, graph)) return NULL; IonSpewPass("DCE"); AssertGraphCoherency(graph); if (mir->shouldCancel("DCE")) return NULL; + if (js_IonOptions.licm) { + LICM licm(mir, graph); + if (!licm.analyze()) + return NULL; + IonSpewPass("LICM"); + AssertGraphCoherency(graph); + + if (mir->shouldCancel("LICM")) + return NULL; + } + if (js_IonOptions.edgeCaseAnalysis) { EdgeCaseAnalysis edgeCaseAnalysis(mir, graph); if (!edgeCaseAnalysis.analyzeLate()) return NULL; IonSpewPass("Edge Case Analysis (Late)"); AssertGraphCoherency(graph); if (mir->shouldCancel("Edge Case Analysis (Late)"))
--- a/js/src/ion/IonAnalysis.cpp +++ b/js/src/ion/IonAnalysis.cpp @@ -807,17 +807,17 @@ typedef HashMap<uint32, BoundsCheckInfo, DefaultHasher<uint32>, IonAllocPolicy> BoundsCheckMap; // Compute a hash for bounds checks which ignores constant offsets in the index. static HashNumber BoundsCheckHashIgnoreOffset(MBoundsCheck *check) { - SimpleLinearSum indexSum = ExtractLinearSum(check->index()); + LinearSum indexSum = ExtractLinearSum(check->index()); uintptr_t index = indexSum.term ? uintptr_t(indexSum.term) : 0; uintptr_t length = uintptr_t(check->length()); return index ^ length; } static MBoundsCheck * FindDominatingBoundsCheck(BoundsCheckMap &checks, MBoundsCheck *check, size_t index) { @@ -835,130 +835,67 @@ FindDominatingBoundsCheck(BoundsCheckMap return check; } return p->value.check; } // Extract a linear sum from ins, if possible (otherwise giving the sum 'ins + 0'). -SimpleLinearSum +LinearSum ion::ExtractLinearSum(MDefinition *ins) { - if (ins->isBeta()) - ins = ins->getOperand(0); - if (ins->type() != MIRType_Int32) - return SimpleLinearSum(ins, 0); + return LinearSum(ins, 0); if (ins->isConstant()) { const Value &v = ins->toConstant()->value(); JS_ASSERT(v.isInt32()); - return SimpleLinearSum(NULL, v.toInt32()); + return LinearSum(NULL, v.toInt32()); } else if (ins->isAdd() || ins->isSub()) { MDefinition *lhs = ins->getOperand(0); MDefinition *rhs = ins->getOperand(1); if (lhs->type() == MIRType_Int32 && rhs->type() == MIRType_Int32) { - SimpleLinearSum lsum = ExtractLinearSum(lhs); - SimpleLinearSum rsum = ExtractLinearSum(rhs); + LinearSum lsum = ExtractLinearSum(lhs); + LinearSum rsum = ExtractLinearSum(rhs); JS_ASSERT(lsum.term || rsum.term); if (lsum.term && rsum.term) - return SimpleLinearSum(ins, 0); + return LinearSum(ins, 0); // Check if this is of the form <SUM> + n, n + <SUM> or <SUM> - n. if (ins->isAdd()) { int32 constant; if (!SafeAdd(lsum.constant, rsum.constant, &constant)) - return SimpleLinearSum(ins, 0); - return SimpleLinearSum(lsum.term ? lsum.term : rsum.term, constant); + return LinearSum(ins, 0); + return LinearSum(lsum.term ? lsum.term : rsum.term, constant); } else if (lsum.term) { int32 constant; if (!SafeSub(lsum.constant, rsum.constant, &constant)) - return SimpleLinearSum(ins, 0); - return SimpleLinearSum(lsum.term, constant); + return LinearSum(ins, 0); + return LinearSum(lsum.term, constant); } } } - return SimpleLinearSum(ins, 0); -} - -// Extract a linear inequality holding when a boolean test goes in the -// specified direction, of the form 'lhs + lhsN <= rhs' (or >=). -bool -ion::ExtractLinearInequality(MTest *test, BranchDirection direction, - SimpleLinearSum *plhs, MDefinition **prhs, bool *plessEqual) -{ - if (!test->getOperand(0)->isCompare()) - return false; - - MCompare *compare = test->getOperand(0)->toCompare(); - - MDefinition *lhs = compare->getOperand(0); - MDefinition *rhs = compare->getOperand(1); - - if (compare->specialization() != MIRType_Int32) - return false; - - JS_ASSERT(lhs->type() == MIRType_Int32); - JS_ASSERT(rhs->type() == MIRType_Int32); - - JSOp jsop = compare->jsop(); - if (direction == FALSE_BRANCH) - jsop = analyze::NegateCompareOp(jsop); - - SimpleLinearSum lsum = ExtractLinearSum(lhs); - SimpleLinearSum rsum = ExtractLinearSum(rhs); - - if (!SafeSub(lsum.constant, rsum.constant, &lsum.constant)) - return false; - - // Normalize operations to use <= or >=. - switch (jsop) { - case JSOP_LE: - *plessEqual = true; - break; - case JSOP_LT: - /* x < y ==> x + 1 <= y */ - if (!SafeAdd(lsum.constant, 1, &lsum.constant)) - return false; - *plessEqual = true; - break; - case JSOP_GE: - *plessEqual = false; - break; - case JSOP_GT: - /* x > y ==> x - 1 >= y */ - if (!SafeSub(lsum.constant, 1, &lsum.constant)) - return false; - *plessEqual = false; - break; - default: - return false; - } - - *plhs = lsum; - *prhs = rsum.term; - - return true; + return LinearSum(ins, 0); } static bool TryEliminateBoundsCheck(MBoundsCheck *dominating, MBoundsCheck *dominated, bool *eliminated) { JS_ASSERT(!*eliminated); // We found two bounds checks with the same hash number, but we still have // to make sure the lengths and index terms are equal. if (dominating->length() != dominated->length()) return true; - SimpleLinearSum sumA = ExtractLinearSum(dominating->index()); - SimpleLinearSum sumB = ExtractLinearSum(dominated->index()); + LinearSum sumA = ExtractLinearSum(dominating->index()); + LinearSum sumB = ExtractLinearSum(dominated->index()); // Both terms should be NULL or the same definition. if (sumA.term != sumB.term) return true; // This bounds check is redundant. *eliminated = true; @@ -1068,84 +1005,8 @@ ion::EliminateRedundantBoundsChecks(MIRG iter++; } index++; } JS_ASSERT(index == graph.numBlocks()); return true; } - -bool -LinearSum::multiply(int32 scale) -{ - for (size_t i = 0; i < terms_.length(); i++) { - if (!SafeMul(scale, terms_[i].scale, &terms_[i].scale)) - return false; - } - return SafeMul(scale, constant_, &constant_); -} - -bool -LinearSum::add(const LinearSum &other) -{ - for (size_t i = 0; i < other.terms_.length(); i++) { - if (!add(other.terms_[i].term, other.terms_[i].scale)) - return false; - } - return add(other.constant_); -} - -bool -LinearSum::add(MDefinition *term, int32 scale) -{ - JS_ASSERT(term); - - if (scale == 0) - return true; - - for (size_t i = 0; i < terms_.length(); i++) { - if (term == terms_[i].term) { - if (!SafeAdd(scale, terms_[i].scale, &terms_[i].scale)) - return false; - if (terms_[i].scale == 0) { - terms_[i] = terms_.back(); - terms_.popBack(); - } - return true; - } - } - - terms_.append(LinearTerm(term, scale)); - return true; -} - -bool -LinearSum::add(int32 constant) -{ - return SafeAdd(constant, constant_, &constant_); -} - -void -LinearSum::print(Sprinter &sp) const -{ - for (size_t i = 0; i < terms_.length(); i++) { - int32 scale = terms_[i].scale; - int32 id = terms_[i].term->id(); - JS_ASSERT(scale); - if (scale > 0) { - if (i) - sp.printf("+"); - if (scale == 1) - sp.printf("#%d", id); - else - sp.printf("%d*#%d", scale, id); - } else if (scale == -1) { - sp.printf("-#%d", id); - } else { - sp.printf("%d*#%d", scale, id); - } - } - if (constant_ > 0) - sp.printf("+%d", constant_); - else if (constant_ < 0) - sp.printf("%d", constant_); -}
--- a/js/src/ion/IonAnalysis.h +++ b/js/src/ion/IonAnalysis.h @@ -6,17 +6,16 @@ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ #ifndef jsion_ion_analysis_h__ #define jsion_ion_analysis_h__ // This file declares various analysis passes that operate on MIR. #include "IonAllocPolicy.h" -#include "MIR.h" namespace js { namespace ion { class MIRGenerator; class MIRGraph; bool @@ -41,76 +40,30 @@ bool BuildPhiReverseMapping(MIRGraph &graph); void AssertGraphCoherency(MIRGraph &graph); bool EliminateRedundantBoundsChecks(MIRGraph &graph); +// Linear sum of term(s). For now the only linear sums which can be represented +// are 'n' or 'x + n' (for any computation x). class MDefinition; -// Simple linear sum of the form 'n' or 'x + n'. -struct SimpleLinearSum +struct LinearSum { MDefinition *term; int32 constant; - SimpleLinearSum(MDefinition *term, int32 constant) + LinearSum(MDefinition *term, int32 constant) : term(term), constant(constant) {} }; -SimpleLinearSum +LinearSum ExtractLinearSum(MDefinition *ins); -bool -ExtractLinearInequality(MTest *test, BranchDirection direction, - SimpleLinearSum *plhs, MDefinition **prhs, bool *plessEqual); - -struct LinearTerm -{ - MDefinition *term; - int32 scale; - - LinearTerm(MDefinition *term, int32 scale) - : term(term), scale(scale) - { - } -}; - -// General linear sum of the form 'x1*n1 + x2*n2 + ... + n' -class LinearSum -{ - public: - LinearSum() - : constant_(0) - { - } - - LinearSum(const LinearSum &other) - : constant_(other.constant_) - { - for (size_t i = 0; i < other.terms_.length(); i++) - terms_.append(other.terms_[i]); - } - - bool multiply(int32 scale); - bool add(const LinearSum &other); - bool add(MDefinition *term, int32 scale); - bool add(int32 constant); - - int32 constant() const { return constant_; } - size_t numTerms() const { return terms_.length(); } - LinearTerm term(size_t i) const { return terms_[i]; } - - void print(Sprinter &sp) const; - - private: - Vector<LinearTerm, 2, IonAllocPolicy> terms_; - int32 constant_; -}; - } // namespace ion } // namespace js #endif // jsion_ion_analysis_h__
--- a/js/src/ion/JSONSpewer.cpp +++ b/js/src/ion/JSONSpewer.cpp @@ -8,17 +8,16 @@ #include <stdarg.h> #include "JSONSpewer.h" #include "LIR.h" #include "TypeOracle.h" #include "MIR.h" #include "MIRGraph.h" #include "LinearScan.h" -#include "RangeAnalysis.h" using namespace js; using namespace js::ion; JSONSpewer::~JSONSpewer() { if (fp_) fclose(fp_); } @@ -251,24 +250,18 @@ JSONSpewer::spewMDef(MDefinition *def) integerValue(def->getOperand(i)->id()); endList(); beginListProperty("uses"); for (MUseDefIterator use(def); use; use++) integerValue(use.def()->id()); endList(); - if (def->range()) { - Sprinter sp(GetIonContext()->cx); - sp.init(); - def->range()->print(sp); - stringProperty("type", "%s : %s", sp.string()); - } else { - stringProperty("type", "%s", StringFromMIRType(def->type())); - } + stringProperty("type", "%s : [%d, %d]", StringFromMIRType(def->type()), + def->range()->lower(), def->range()->upper()); if (def->isInstruction()) { if (MResumePoint *rp = def->toInstruction()->resumePoint()) spewMResumePoint(rp); } endObject(); }
--- a/js/src/ion/LICM.cpp +++ b/js/src/ion/LICM.cpp @@ -12,16 +12,74 @@ #include "IonSpewer.h" #include "LICM.h" #include "MIR.h" #include "MIRGraph.h" using namespace js; using namespace js::ion; +bool +ion::ExtractLinearInequality(MTest *test, BranchDirection direction, + LinearSum *plhs, MDefinition **prhs, bool *plessEqual) +{ + if (!test->getOperand(0)->isCompare()) + return false; + + MCompare *compare = test->getOperand(0)->toCompare(); + + MDefinition *lhs = compare->getOperand(0); + MDefinition *rhs = compare->getOperand(1); + + if (compare->specialization() != MIRType_Int32) + return false; + + JS_ASSERT(lhs->type() == MIRType_Int32); + JS_ASSERT(rhs->type() == MIRType_Int32); + + JSOp jsop = compare->jsop(); + if (direction == FALSE_BRANCH) + jsop = analyze::NegateCompareOp(jsop); + + LinearSum lsum = ExtractLinearSum(lhs); + LinearSum rsum = ExtractLinearSum(rhs); + + if (!SafeSub(lsum.constant, rsum.constant, &lsum.constant)) + return false; + + // Normalize operations to use <= or >=. + switch (jsop) { + case JSOP_LE: + *plessEqual = true; + break; + case JSOP_LT: + /* x < y ==> x + 1 <= y */ + if (!SafeAdd(lsum.constant, 1, &lsum.constant)) + return false; + *plessEqual = true; + break; + case JSOP_GE: + *plessEqual = false; + break; + case JSOP_GT: + /* x > y ==> x - 1 >= y */ + if (!SafeSub(lsum.constant, 1, &lsum.constant)) + return false; + *plessEqual = false; + break; + default: + return false; + } + + *plhs = lsum; + *prhs = rsum.term; + + return true; +} + LICM::LICM(MIRGenerator *mir, MIRGraph &graph) : mir(mir), graph(graph) { } bool LICM::analyze() { @@ -115,16 +173,17 @@ Loop::iterateLoopBlocks(MBasicBlock *cur } return LoopReturn_Success; } bool Loop::optimize() { InstructionQueue invariantInstructions; + InstructionQueue boundsChecks; IonSpew(IonSpew_LICM, "These instructions are in the loop: "); while (!worklist_.empty()) { if (mir->shouldCancel("LICM (worklist)")) return false; MInstruction *ins = popFromWorklist(); @@ -156,43 +215,93 @@ Loop::optimize() if (isInLoop(consumer) && isHoistable(consumer)) { if (!insertInWorklist(consumer->toInstruction())) return false; } } if (IonSpewEnabled(IonSpew_LICM)) fprintf(IonSpewFile, " Loop Invariant!\n"); + } else if (ins->isBoundsCheck()) { + if (!boundsChecks.append(ins)) + return false; } } - if (!hoistInstructions(invariantInstructions)) + if (!hoistInstructions(invariantInstructions, boundsChecks)) return false; return true; } bool -Loop::hoistInstructions(InstructionQueue &toHoist) +Loop::hoistInstructions(InstructionQueue &toHoist, InstructionQueue &boundsChecks) { + // Hoist bounds checks first, so that hoistBoundsCheck can test for + // invariant instructions, but delay actual insertion until the end to + // handle dependencies on loop invariant instructions. + InstructionQueue hoistedChecks; + for (size_t i = 0; i < boundsChecks.length(); i++) { + MBoundsCheck *ins = boundsChecks[i]->toBoundsCheck(); + if (isLoopInvariant(ins) || !isInLoop(ins)) + continue; + + // Try to find a test dominating the bounds check which can be + // transformed into a hoistable check. Stop after the first such check + // which could be transformed (the one which will be the closest to the + // access in the source). + MBasicBlock *block = ins->block(); + while (true) { + BranchDirection direction; + MTest *branch = block->immediateDominatorBranch(&direction); + if (branch) { + MInstruction *upper, *lower; + tryHoistBoundsCheck(ins, branch, direction, &upper, &lower); + if (upper && !hoistedChecks.append(upper)) + return false; + if (lower && !hoistedChecks.append(lower)) + return false; + if (upper || lower) { + // Note: replace all uses of the original bounds check with the + // actual index. This is usually done during bounds check elimination, + // but in this case it's safe to do it here since the load/store is + // definitely not loop-invariant, so we will never move it before + // one of the bounds checks we just added. + ins->replaceAllUsesWith(ins->index()); + ins->block()->discard(ins); + break; + } + } + MBasicBlock *dom = block->immediateDominator(); + if (dom == block) + break; + block = dom; + } + } + // Move all instructions to the preLoop_ block just before the control instruction. for (size_t i = 0; i < toHoist.length(); i++) { MInstruction *ins = toHoist[i]; // Loads may have an implicit dependency on either stores (effectful instructions) or // control instructions so we should never move these. JS_ASSERT(!ins->isControlInstruction()); JS_ASSERT(!ins->isEffectful()); JS_ASSERT(ins->isMovable()); if (checkHotness(ins->block())) { ins->block()->moveBefore(preLoop_->lastIns(), ins); ins->setNotLoopInvariant(); } } + for (size_t i = 0; i < hoistedChecks.length(); i++) { + MInstruction *ins = hoistedChecks[i]; + preLoop_->insertBefore(preLoop_->lastIns(), ins); + } + return true; } bool Loop::isInLoop(MDefinition *ins) { return ins->block()->id() >= header_->id(); } @@ -256,8 +365,191 @@ Loop::insertInWorklist(MInstruction *ins MInstruction* Loop::popFromWorklist() { MInstruction* toReturn = worklist_.popCopy(); toReturn->setNotInWorklist(); return toReturn; } + +// Try to compute hoistable checks for the upper and lower bound on ins, +// according to a test in the loop which dominates ins. +// +// Given a bounds check within a loop which is not loop invariant, we would +// like to compute loop invariant bounds checks which imply that the inner +// check will succeed. These invariant checks can then be added to the +// preheader, and the inner check eliminated. +// +// Example: +// +// for (i = v; i < n; i++) +// x[i] = 0; +// +// There are two constraints captured by the bounds check here: i >= 0, and +// i < length(x). 'i' is not loop invariant, but we can still hoist these +// checks: +// +// - At the point of the check, it is known that i < n. Given this, +// if n <= length(x) then i < length(x), and since n and length(x) are loop +// invariant the former condition can be hoisted and the i < length(x) check +// removed. +// +// - i is only incremented within the loop, so if its initial value is >= 0 +// then all its values within the loop will also be >= 0. The lower bounds +// check can be hoisted as v >= 0. +// +// tryHoistBoundsCheck encodes this logic. Given a bounds check B and a test T +// in the loop dominating that bounds check, where B and T share a non-invariant +// term lhs, a new check C is computed such that T && C imply B. +void +Loop::tryHoistBoundsCheck(MBoundsCheck *ins, MTest *test, BranchDirection direction, + MInstruction **pupper, MInstruction **plower) +{ + *pupper = NULL; + *plower = NULL; + + if (!isLoopInvariant(ins->length())) + return; + + LinearSum lhs(NULL, 0); + MDefinition *rhs; + bool lessEqual; + if (!ExtractLinearInequality(test, direction, &lhs, &rhs, &lessEqual)) + return; + + // Ensure the rhs is a loop invariant term. + if (rhs && !isLoopInvariant(rhs)) { + if (lhs.term && !isLoopInvariant(lhs.term)) + return; + MDefinition *temp = lhs.term; + lhs.term = rhs; + rhs = temp; + if (!SafeSub(0, lhs.constant, &lhs.constant)) + return; + lessEqual = !lessEqual; + } + + JS_ASSERT_IF(rhs, isLoopInvariant(rhs)); + + // Ensure the lhs is a phi node from the start of the loop body. + if (!lhs.term || !lhs.term->isPhi() || lhs.term->block() != header_) + return; + + // Check if the lhs in the conditional matches the bounds check index. + LinearSum index = ExtractLinearSum(ins->index()); + if (index.term != lhs.term) + return; + + if (!lessEqual) + return; + + // At the point of the access, it is known that lhs + lhsN <= rhs, and the + // bounds check is that lhs + indexN + maximum < length. To ensure the + // bounds check holds then, we need to ensure that: + // + // rhs - lhsN + indexN + maximum < length + + int32 adjustment; + if (!SafeSub(index.constant, lhs.constant, &adjustment)) + return; + if (!SafeAdd(adjustment, ins->maximum(), &adjustment)) + return; + + // For the lower bound, check that lhs + indexN + minimum >= 0, e.g. + // + // lhs >= -indexN - minimum + // + // lhs is not loop invariant, but if this condition holds of the backing + // variable at loop entry and the variable's value never decreases in the + // loop body, it will hold throughout the loop. + + uint32 position = preLoop_->positionInPhiSuccessor(); + MDefinition *initialIndex = lhs.term->toPhi()->getOperand(position); + if (!nonDecreasing(initialIndex, lhs.term)) + return; + + int32 lowerBound; + if (!SafeSub(0, index.constant, &lowerBound)) + return; + if (!SafeSub(lowerBound, ins->minimum(), &lowerBound)) + return; + + // XXX limit on how much can be hoisted, to ensure ballast works? + + if (!rhs) { + rhs = MConstant::New(Int32Value(adjustment)); + adjustment = 0; + preLoop_->insertBefore(preLoop_->lastIns(), rhs->toInstruction()); + } + + MBoundsCheck *upper = MBoundsCheck::New(rhs, ins->length()); + upper->setMinimum(adjustment); + upper->setMaximum(adjustment); + + MBoundsCheckLower *lower = MBoundsCheckLower::New(initialIndex); + lower->setMinimum(lowerBound); + + *pupper = upper; + *plower = lower; +} + +// Determine whether the possible value of start (a phi node within the loop) +// can become smaller than an initial value at loop entry. +bool +Loop::nonDecreasing(MDefinition *initial, MDefinition *start) +{ + MDefinitionVector worklist; + MDefinitionVector seen; + + if (!worklist.append(start)) + return false; + + while (!worklist.empty()) { + MDefinition *def = worklist.popCopy(); + bool duplicate = false; + for (size_t i = 0; i < seen.length() && !duplicate; i++) { + if (seen[i] == def) + duplicate = true; + } + if (duplicate) + continue; + if (!seen.append(def)) + return false; + + if (def->type() != MIRType_Int32) + return false; + + if (!isInLoop(def)) { + if (def != initial) + return false; + continue; + } + + if (def->isPhi()) { + MPhi *phi = def->toPhi(); + for (size_t i = 0; i < phi->numOperands(); i++) { + if (!worklist.append(phi->getOperand(i))) + return false; + } + continue; + } + + if (def->isAdd()) { + if (def->toAdd()->specialization() != MIRType_Int32) + return false; + MDefinition *lhs = def->toAdd()->getOperand(0); + MDefinition *rhs = def->toAdd()->getOperand(1); + if (!rhs->isConstant()) + return false; + Value v = rhs->toConstant()->value(); + if (!v.isInt32() || v.toInt32() < 0) + return false; + if (!worklist.append(lhs)) + return false; + continue; + } + + return false; + } + + return true; +}
--- a/js/src/ion/LICM.h +++ b/js/src/ion/LICM.h @@ -28,16 +28,22 @@ class LICM MIRGenerator *mir; MIRGraph &graph; public: LICM(MIRGenerator *mir, MIRGraph &graph); bool analyze(); }; +// Extract a linear inequality holding when a boolean test goes in the +// specified direction, of the form 'lhs + lhsN <= rhs' (or >=). +bool +ExtractLinearInequality(MTest *test, BranchDirection direction, + LinearSum *plhs, MDefinition **prhs, bool *plessEqual); + class Loop { MIRGenerator *mir; MIRGraph &graph; public: // Loop code may return three values: enum LoopReturn { @@ -66,17 +72,17 @@ class Loop // the loop is first entered and where hoisted instructions will be placed. MBasicBlock* preLoop_; // This method recursively traverses the graph from the loop footer back through // predecessor edges and stops when it reaches the loop header. // Along the way it adds instructions to the worklist for invariance testing. LoopReturn iterateLoopBlocks(MBasicBlock *current); - bool hoistInstructions(InstructionQueue &toHoist); + bool hoistInstructions(InstructionQueue &toHoist, InstructionQueue &boundsChecks); // Utility methods for invariance testing and instruction hoisting. bool isInLoop(MDefinition *ins); bool isLoopInvariant(MInstruction *ins); bool isLoopInvariant(MDefinition *ins); // This method determines if this block hot within a loop. That is, if it's // always or usually run when the loop executes @@ -85,14 +91,23 @@ class Loop // Worklist and worklist usage methods InstructionQueue worklist_; bool insertInWorklist(MInstruction *ins); MInstruction* popFromWorklist(); inline bool isHoistable(const MDefinition *ins) const { return ins->isMovable() && !ins->isEffectful(); } + + // State for hoisting bounds checks. Even if the terms involved in a bounds + // check are not loop invariant, we analyze the tests and increments done + // in the loop to try to find a stronger condition which can be hoisted. + + void tryHoistBoundsCheck(MBoundsCheck *ins, MTest *test, BranchDirection direction, + MInstruction **pupper, MInstruction **plower); + + bool nonDecreasing(MDefinition *initial, MDefinition *start); }; } // namespace ion } // namespace js #endif // jsion_licm_h__
--- a/js/src/ion/Lowering.cpp +++ b/js/src/ion/Lowering.cpp @@ -5,17 +5,16 @@ * 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 "LIR.h" #include "Lowering.h" #include "MIR.h" #include "MIRGraph.h" #include "IonSpewer.h" -#include "RangeAnalysis.h" #include "jsanalyze.h" #include "jsbool.h" #include "jsnum.h" #include "jsobjinlines.h" #include "shared/Lowering-shared-inl.h" using namespace js; using namespace ion;
--- a/js/src/ion/MIR.cpp +++ b/js/src/ion/MIR.cpp @@ -5,17 +5,16 @@ * 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 "IonBuilder.h" #include "LICM.h" // For LinearSum #include "MIR.h" #include "MIRGraph.h" #include "EdgeCaseAnalysis.h" -#include "RangeAnalysis.h" #include "IonSpewer.h" #include "jsnum.h" #include "jsstr.h" #include "jsatominlines.h" #include "jstypedarrayinlines.h" // For ClampIntForUint8Array using namespace js; using namespace js::ion; @@ -280,16 +279,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; @@ -467,16 +471,63 @@ MPhi::congruentTo(MDefinition *const &in bool MPhi::addInput(MDefinition *ins) { ins->addUse(this, inputs_.length()); return inputs_.append(ins); } +bool +MPhi::recomputeRange() +{ + if (type() != MIRType_Int32) + return false; + + // Use RangeUpdater rather than Range because it needs to + // track if it has been updated yet. + RangeUpdater r; + JS_ASSERT(getOperand(0)->op() != MDefinition::Op_OsrValue); + bool updated = false; + for (size_t i = 0; i < numOperands(); i++) { + if (getOperand(i)->block()->earlyAbort()) { + IonSpew(IonSpew_Range, "Ignoring unreachable input %d", getOperand(i)->id()); + continue; + } + + if (!isOSRLikeValue(getOperand(i))) { + if (block()->isLoopHeader()) { + IonSpew(IonSpew_Range, " Updating input #%d (inst %d)", i, getOperand(i)->id()); + changeCounts_[i].updateRange(getOperand(i)->range()); + r.unionWith(&changeCounts_[i]); + } else { + r.unionWith(getOperand(i)->range()); + } + +#ifdef DEBUG + if (IonSpewEnabled(IonSpew_Range)) { + fprintf(IonSpewFile, " %d:", getOperand(i)->id()); + getOperand(i)->range()->printRange(IonSpewFile); + fprintf(IonSpewFile, " => "); + r.printRange(IonSpewFile); + fprintf(IonSpewFile, "\n"); + } +#endif + + + } + } + if (!updated) { + IonSpew(IonSpew_Range, "My block is unreachable %d", id()); + block()->setEarlyAbort(); + return false; + } + return range()->update(r.getRange()); +} + uint32 MPrepareCall::argc() const { JS_ASSERT(useCount() == 1); MCall *call = usesBegin()->node()->toDefinition()->toCall(); return call->numStackArgs(); } @@ -838,22 +889,16 @@ MAdd::updateForReplacement(MDefinition * { JS_ASSERT(ins_->isAdd()); MAdd *ins = ins_->toAdd(); if (isTruncated()) setTruncated(ins->isTruncated()); return true; } -bool -MAdd::fallible() -{ - return !isTruncated() && (!range() || !range()->isFinite()); -} - void MSub::analyzeTruncateBackward() { if (!isTruncated()) setTruncated(js::ion::EdgeCaseAnalysis::AllUsesTruncate(this)); } bool @@ -861,22 +906,16 @@ MSub::updateForReplacement(MDefinition * { JS_ASSERT(ins_->isSub()); MSub *ins = ins_->toSub(); if (isTruncated()) setTruncated(ins->isTruncated()); return true; } -bool -MSub::fallible() -{ - return !isTruncated() && (!range() || !range()->isFinite()); -} - MDefinition * MMul::foldsTo(bool useValueNumbers) { MDefinition *out = MBinaryArithInstruction::foldsTo(useValueNumbers); if (out != this) return out; if (specialization() != MIRType_Int32) @@ -931,34 +970,16 @@ MMul::updateForReplacement(MDefinition * { JS_ASSERT(ins_->isMul()); MMul *ins = ins_->toMul(); if (isPossibleTruncated()) setPossibleTruncated(ins->isPossibleTruncated()); return true; } -bool -MMul::canOverflow() -{ - if (implicitTruncate_) - return false; - return !range() || !range()->isFinite(); -} - -bool -MMul::canBeNegativeZero() -{ - if (!range()) - return canBeNegativeZero_; - if (range()->lower() > 0 || range()->upper() < 0) - return false; - return canBeNegativeZero_; -} - void MBinaryArithInstruction::infer(JSContext *cx, const TypeOracle::BinaryTypes &b) { // Retrieve type information of lhs and rhs // Rhs is defaulted to int32 first, // because in some cases there is no rhs type information MIRType lhs = MIRTypeFromValueType(b.lhsTypes->getKnownTypeTag()); MIRType rhs = MIRType_Int32; @@ -1504,41 +1525,29 @@ MNot::foldsTo(bool useValueNumbers) // NOT of an undefined or null value is always true if (operand()->type() == MIRType_Undefined || operand()->type() == MIRType_Null) return MConstant::New(BooleanValue(true)); return this; } -bool -MBoundsCheckLower::fallible() -{ - return !range() || range()->lower() < minimum_; -} - void MBeta::printOpcode(FILE *fp) { PrintOpcodeName(fp, op()); fprintf(fp, " "); getOperand(0)->printName(fp); fprintf(fp, " "); - - Sprinter sp(GetIonContext()->cx); - sp.init(); - comparison_->print(sp); - fprintf(fp, "%s", sp.string()); + comparison_.printRange(fp); } -void -MBeta::computeRange() +bool +MBeta::recomputeRange() { - bool emptyRange = false; - - Range *range = Range::intersect(val_->range(), comparison_, &emptyRange); - if (emptyRange) { - IonSpew(IonSpew_Range, "Marking block for inst %d unexitable", id()); - block()->setEarlyAbort(); - } else { - setRange(range); + bool nullRange = false; + bool ret = range()->update(Range::intersect(val_->range(), &comparison_, &nullRange)); + if (nullRange) { + IonSpew(IonSpew_Range, "Marking block for inst %d unexitable", id()); + block()->setEarlyAbort(); } + return ret; }
--- a/js/src/ion/MIR.h +++ b/js/src/ion/MIR.h @@ -19,24 +19,22 @@ #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; -class Range; - static const inline MIRType MIRTypeFromValue(const js::Value &vp) { if (vp.isDouble()) return MIRType_Double; return MIRTypeFromValueType(vp.extractNonDoubleType()); } @@ -225,17 +223,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) - Range *range_; // Any computed range for this def. + + // 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. }; @@ -285,37 +287,33 @@ class MDefinition : public MNode void setTrackedPc(jsbytecode *pc) { trackedPc_ = pc; } jsbytecode *trackedPc() { return trackedPc_; } - Range *range() const { - return range_; - } - void setRange(Range *range) { - range_ = range; + 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(); bool earlyAbortCheck(); - - // Compute an absolute or symbolic range for the value of this node. - // Ranges are only computed for definitions whose type is int32. - virtual void computeRange() { + // 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_); @@ -620,18 +618,16 @@ class MConstant : public MNullaryInstruc void printOpcode(FILE *fp); HashNumber valueHash() const; bool congruentTo(MDefinition * const &ins) const; AliasSet getAliasSet() const { return AliasSet::None(); } - - void computeRange(); }; class MParameter : public MNullaryInstruction { int32 index_; types::StackTypeSet *typeSet_; public: @@ -851,27 +847,16 @@ class MGoto : public MAryControlInstruct MBasicBlock *target() { return getSuccessor(0); } AliasSet getAliasSet() const { return AliasSet::None(); } }; -enum BranchDirection { - FALSE_BRANCH, - TRUE_BRANCH -}; - -static inline BranchDirection -NegateBranchDirection(BranchDirection dir) -{ - return (dir == FALSE_BRANCH) ? TRUE_BRANCH : FALSE_BRANCH; -} - // Tests if the input instruction evaluates to true or false, and jumps to the // start of a corresponding basic block. class MTest : public MAryControlInstruction<1, 2>, public TestPolicy { MTest(MDefinition *ins, MBasicBlock *if_true, MBasicBlock *if_false) { initOperand(0, ins); @@ -885,19 +870,16 @@ class MTest MBasicBlock *ifTrue, MBasicBlock *ifFalse); MBasicBlock *ifTrue() const { return getSuccessor(0); } MBasicBlock *ifFalse() const { return getSuccessor(1); } - MBasicBlock *branchSuccessor(BranchDirection dir) const { - return (dir == TRUE_BRANCH) ? ifTrue() : ifFalse(); - } TypePolicy *typePolicy() { return this; } AliasSet getAliasSet() const { return AliasSet::None(); } MDefinition *foldsTo(bool useValueNumbers); @@ -1714,16 +1696,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); } @@ -1754,16 +1737,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); } @@ -1819,16 +1803,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; @@ -1914,16 +1899,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); @@ -1956,17 +1942,22 @@ class MBitAnd : public MBinaryBitwiseIns return getOperand(operand); // 0 & x => 0; } MDefinition *foldIfNegOne(size_t operand) { return getOperand(1 - operand); // x & -1 => x } MDefinition *foldIfEqual() { return getOperand(0); // x & x => x; } - void computeRange(); + bool recomputeRange() { + Range *left = getOperand(0)->range(); + Range *right = getOperand(1)->range(); + return range()->update(Range::and_(left, right)); + } + }; class MBitOr : public MBinaryBitwiseInstruction { MBitOr(MDefinition *left, MDefinition *right) : MBinaryBitwiseInstruction(left, right) { } @@ -2035,17 +2026,25 @@ class MLsh : public MShiftInstruction static MLsh *New(MDefinition *left, MDefinition *right); MDefinition *foldIfZero(size_t operand) { // 0 << x => 0 // x << 0 => x return getOperand(0); } - void computeRange(); + 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) { } @@ -2053,17 +2052,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); } - void computeRange(); + 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), @@ -2128,21 +2135,16 @@ class MBinaryArithInstruction } MDefinition *foldsTo(bool useValueNumbers); virtual double getIdentity() = 0; void infer(JSContext *cx, const TypeOracle::BinaryTypes &b); - void setInt32() { - specialization_ = MIRType_Int32; - setResultType(MIRType_Int32); - } - bool congruentTo(MDefinition *const &ins) const { return MBinaryInstruction::congruentTo(ins); } AliasSet getAliasSet() const { if (specialization_ >= MIRType_Object) return AliasSet::Store(AliasSet::Any); return AliasSet::None(); } @@ -2219,17 +2221,27 @@ class MAbs } bool congruentTo(MDefinition *const &ins) const { return congruentIfOperandsEqual(ins); } AliasSet getAliasSet() const { return AliasSet::None(); } - void computeRange(); + 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); + } }; // Inline implementation of Math.sqrt(). class MSqrt : public MUnaryInstruction, public DoublePolicy<0> { MSqrt(MDefinition *num) @@ -2422,18 +2434,28 @@ class MAdd : public MBinaryArithInstruct void setTruncated(bool val) { implicitTruncate_ = val; } bool updateForReplacement(MDefinition *ins); double getIdentity() { return 0; } - bool fallible(); - void computeRange(); + bool fallible() { + return !isTruncated() && !range()->isFinite(); + } + + bool recomputeRange() { + if (specialization() != MIRType_Int32) + return false; + Range *left = getOperand(0)->range(); + Range *right = getOperand(1)->range(); + Range next = isTruncated() ? Range::addTruncate(left,right) : Range::add(left, right); + return range()->update(next); + } }; class MSub : public MBinaryArithInstruction { bool implicitTruncate_; MSub(MDefinition *left, MDefinition *right) : MBinaryArithInstruction(left, right), implicitTruncate_(false) @@ -2455,18 +2477,28 @@ class MSub : public MBinaryArithInstruct implicitTruncate_ = val; } bool updateForReplacement(MDefinition *ins); double getIdentity() { return 0; } - bool fallible(); - void computeRange(); + bool fallible() { + return !isTruncated() && !range()->isFinite(); + } + + bool recomputeRange() { + if (specialization() != MIRType_Int32) + return false; + Range *left = getOperand(0)->range(); + Range *right = getOperand(1)->range(); + Range next = isTruncated() ? Range::subTruncate(left,right) : Range::sub(left, right); + return range()->update(next); + } }; class MMul : public MBinaryArithInstruction { // Annotation the result could be a negative zero // and we need to guard this during execution. bool canBeNegativeZero_; @@ -2503,26 +2535,40 @@ class MMul : public MBinaryArithInstruct void analyzeEdgeCasesForward(); void analyzeEdgeCasesBackward(); void analyzeTruncateBackward(); double getIdentity() { return 1; } - bool canOverflow(); - bool canBeNegativeZero(); - + bool canOverflow() { + return !implicitTruncate_ && !range()->isFinite(); + } + + bool canBeNegativeZero() { + if (range()->lower() > 0 || range()->upper() < 0) + return false; + return canBeNegativeZero_; + } bool updateForReplacement(MDefinition *ins); bool fallible() { return canBeNegativeZero_ || canOverflow(); } - void computeRange(); + bool recomputeRange() { + if (specialization() != MIRType_Int32) + return false; + Range *left = getOperand(0)->range(); + Range *right = getOperand(1)->range(); + if (isPossibleTruncated()) + implicitTruncate_ = !Range::precisionLossMul(left, right); + return range()->update(Range::mul(left, right)); + } bool isPossibleTruncated() const { return possibleTruncate_; } void setPossibleTruncated(bool truncate) { possibleTruncate_ = truncate; } @@ -2604,17 +2650,31 @@ class MMod : public MBinaryArithInstruct } MDefinition *foldsTo(bool useValueNumbers); double getIdentity() { JS_NOT_REACHED("not used"); return 1; } - void computeRange(); + bool recomputeRange() { + if (specialization() != MIRType_Int32) + return false; + Range *rhs = getOperand(1)->range(); + int64_t a = Range::abs64((int64_t)rhs->lower()); + int64_t b = Range::abs64((int64_t)rhs->upper()); + if (a ==0 && b == 0) { + // We should never take something % 0. + Range r(INT_MIN, INT_MAX); + return range()->update(r); + } + int64_t bound = Max(1-a, b-1); + Range r(-bound, bound); + return range()->update(r); + } }; class MConcat : public MBinaryInstruction, public BinaryStringPolicy { MConcat(MDefinition *left, MDefinition *right) : MBinaryInstruction(left, right) @@ -2644,16 +2704,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); } @@ -2661,18 +2723,16 @@ class MCharCodeAt TypePolicy *typePolicy() { return this; } virtual AliasSet getAliasSet() const { // Strings are immutable, so there is no implicit dependency. return AliasSet::None(); } - - void computeRange(); }; class MFromCharCode : public MUnaryInstruction, public IntPolicy<0> { MFromCharCode(MDefinition *code) : MUnaryInstruction(code) @@ -2695,16 +2755,19 @@ class MFromCharCode class MPhi : public MDefinition, public InlineForwardListNode<MPhi> { js::Vector<MDefinition *, 2, IonAllocPolicy> inputs_; uint32 slot_; bool triedToSpecialize_; bool hasBytecodeUses_; bool isIterator_; + // For every input to the phi, track how many times it has changed + // Only used in loop headers, so it defaults to 0 elements to conserve space + js::Vector<RangeChangeCount, 0, IonAllocPolicy> changeCounts_; MPhi(uint32 slot) : slot_(slot), triedToSpecialize_(false), hasBytecodeUses_(false), isIterator_(false) { setResultType(MIRType_Value); } @@ -2751,47 +2814,49 @@ class MPhi : public MDefinition, public } void setIterator() { isIterator_ = true; } AliasSet getAliasSet() const { return AliasSet::None(); } - void computeRange(); + bool recomputeRange(); + bool initCounts() { + return changeCounts_.resize(inputs_.length()); + } }; // 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: - const Range *comparison_; + Range comparison_; MDefinition *val_; - MBeta(MDefinition *val, const Range *comp) + MBeta(MDefinition *val, const Range &comp) : MUnaryInstruction(val), comparison_(comp), val_(val) { - setResultType(val->type()); } public: INSTRUCTION_HEADER(Beta); void printOpcode(FILE *fp); - static MBeta *New(MDefinition *val, const Range *comp) + static MBeta *New(MDefinition *val, const Range &comp) { return new MBeta(val, comp); } AliasSet getAliasSet() const { return AliasSet::None(); } - void computeRange(); + bool recomputeRange(); }; // MIR representation of a Value on the OSR StackFrame. // The Value is indexed off of OsrFrameReg. class MOsrValue : public MUnaryInstruction { private: ptrdiff_t frameOffset_; @@ -3439,17 +3504,19 @@ class MBoundsCheckLower return minimum_; } void setMinimum(int32 n) { minimum_ = n; } AliasSet getAliasSet() const { return AliasSet::None(); } - bool fallible(); + 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 { @@ -3915,16 +3982,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); } @@ -3938,17 +4006,16 @@ class MClampToUint8 return this; } bool congruentTo(MDefinition *const &ins) const { return congruentIfOperandsEqual(ins); } AliasSet getAliasSet() const { return AliasSet::None(); } - void computeRange(); }; class MLoadFixedSlot : public MUnaryInstruction, public SingleObjectPolicy { size_t slot_;
--- a/js/src/ion/MIRGraph.h +++ b/js/src/ion/MIRGraph.h @@ -25,16 +25,21 @@ class MStart; class MDefinitionIterator; typedef InlineListIterator<MInstruction> MInstructionIterator; typedef InlineListReverseIterator<MInstruction> MInstructionReverseIterator; typedef InlineForwardListIterator<MPhi> MPhiIterator; class LBlock; +enum BranchDirection { + FALSE_BRANCH, + TRUE_BRANCH +}; + class MBasicBlock : public TempObject, public InlineListNode<MBasicBlock> { public: enum Kind { NORMAL, PENDING_LOOP_HEADER, LOOP_HEADER, SPLIT_EDGE
--- a/js/src/ion/RangeAnalysis.cpp +++ b/js/src/ion/RangeAnalysis.cpp @@ -3,17 +3,16 @@ * * 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 "IonAnalysis.h" #include "MIR.h" #include "MIRGraph.h" #include "RangeAnalysis.h" #include "IonSpewer.h" using namespace js; using namespace js::ion; @@ -91,21 +90,21 @@ IsDominatedUse(MBasicBlock *block, MUse return block->dominates(n->block()); } static inline void SpewRange(MDefinition *def) { #ifdef DEBUG - if (IonSpewEnabled(IonSpew_Range) && def->range()) { - Sprinter sp(GetIonContext()->cx); - sp.init(); - def->range()->print(sp); - IonSpew(IonSpew_Range, "%d has range %s", def->id(), sp.string()); + 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) { @@ -158,20 +157,20 @@ RangeAnalysis::addBetaNobes() smaller = left; greater = right; } else if (jsop == JSOP_GT) { smaller = right; greater = left; } if (smaller && greater) { MBeta *beta; - beta = MBeta::New(smaller, new Range(JSVAL_INT_MIN, JSVAL_INT_MAX-1)); + beta = MBeta::New(smaller, Range(JSVAL_INT_MIN, JSVAL_INT_MAX-1)); block->insertBefore(*block->begin(), beta); replaceDominatedUsesWith(smaller, beta, block); - beta = MBeta::New(greater, new Range(JSVAL_INT_MIN+1, JSVAL_INT_MAX)); + beta = MBeta::New(greater, Range(JSVAL_INT_MIN+1, JSVAL_INT_MAX)); block->insertBefore(*block->begin(), beta); replaceDominatedUsesWith(greater, beta, block); } continue; } JS_ASSERT(val); @@ -198,17 +197,17 @@ RangeAnalysis::addBetaNobes() comp.setLower(bound); comp.setUpper(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, new Range(comp)); + MBeta *beta = MBeta::New(val, comp); block->insertBefore(*block->begin(), beta); replaceDominatedUsesWith(val, beta, block); } return true; } bool @@ -233,237 +232,219 @@ RangeAnalysis::removeBetaNobes() break; } } } return true; } void -SymbolicBound::print(Sprinter &sp) const -{ - if (loop) - sp.printf("[loop] "); - sum.print(sp); -} - -void -Range::print(Sprinter &sp) const +Range::printRange(FILE *fp) { JS_ASSERT_IF(lower_infinite_, lower_ == JSVAL_INT_MIN); JS_ASSERT_IF(upper_infinite_, upper_ == JSVAL_INT_MAX); - - sp.printf("["); - - if (lower_infinite_) - sp.printf("-inf"); - else - sp.printf("%d", lower_); - if (symbolicLower_) { - sp.printf(" {"); - symbolicLower_->print(sp); - sp.printf("}"); - } - - sp.printf(", "); - - if (upper_infinite_) - sp.printf("inf"); - else - sp.printf("%d", upper_); - if (symbolicUpper_) { - sp.printf(" {"); - symbolicUpper_->print(sp); - sp.printf("}"); - } - - sp.printf("]"); + 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, bool *emptyRange) +Range +Range::intersect(const Range *lhs, const Range *rhs, bool *nullRange) { - *emptyRange = false; - - if (!lhs && !rhs) - return NULL; - - if (!lhs) - return new Range(*rhs); - if (!rhs) - return new Range(*lhs); - - Range *r = new Range( + 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_; + 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_) { - *emptyRange = true; - r->makeRangeInfinite(); + if (r.upper_ < r.lower_) { + *nullRange = true; + r.makeRangeInfinite(); } - return r; } void Range::unionWith(const Range *other) { setLower(Min(lower_, other->lower_)); lower_infinite_ |= other->lower_infinite_; setUpper(Max(upper_, other->upper_)); upper_infinite_ |= other->upper_infinite_; } -static const Range emptyRange; - -static inline void -EnsureRange(const Range **prange) +void +RangeUpdater::updateLower(const Range *other) { - if (!*prange) - *prange = &emptyRange; + if (lowerSet_) { + r_.setLower(Min(r_.lower(), other->lower())); + } else { + r_.setLower(other->lower()); + lowerSet_ = true; + } + if (other->isLowerInfinite()) + r_.makeLowerInfinite(); } - -Range * -Range::add(const Range *lhs, const Range *rhs) +void +RangeUpdater::updateUpper(const Range *other) { - EnsureRange(&lhs); - EnsureRange(&rhs); - return new Range( - (int64_t)lhs->lower_ + (int64_t)rhs->lower_, - (int64_t)lhs->upper_ + (int64_t)rhs->upper_); + if (upperSet_) { + r_.setUpper(Min(r_.upper(), other->upper())); + } else { + r_.setUpper(other->upper()); + upperSet_ = true; + } + if (other->isUpperInfinite()) + r_.makeUpperInfinite(); } -Range * -Range::sub(const Range *lhs, const Range *rhs) +void +RangeUpdater::unionWith(const Range *other) { - EnsureRange(&lhs); - EnsureRange(&rhs); - return new Range( - (int64_t)lhs->lower_ - (int64_t)rhs->upper_, - (int64_t)lhs->upper_ - (int64_t)rhs->lower_); + updateLower(other); + updateUpper(other); } -/* static */ Range * -Range::Truncate(int64_t l, int64_t h) +void +RangeUpdater::unionWith(RangeChangeCount *other) { - Range *ret = new Range(l, h); - if (!ret->isFinite()) { - ret->makeLowerInfinite(); - ret->makeUpperInfinite(); + if (other->lowerCount_ <= 2) { + // If this->lower has been initialized, then update it + // otherwise, initialize it. + updateLower(&other->oldRange); + } else { + other->lowerCount_ = 0; } + + if (other->upperCount_ <= 2) { + updateUpper(&other->oldRange); + } else { + other->upperCount_ = 0; + } +} + +Range +Range::add(const Range *lhs, const Range *rhs) +{ + Range ret( + (int64_t)lhs->lower_ + (int64_t)rhs->lower_, + (int64_t)lhs->upper_ + (int64_t)rhs->upper_); return ret; } -Range * +Range +Range::sub(const Range *lhs, const Range *rhs) +{ + Range ret( + (int64_t)lhs->lower_ - (int64_t)rhs->upper_, + (int64_t)lhs->upper_ - (int64_t)rhs->lower_); + return ret; + +} +Range Range::addTruncate(const Range *lhs, const Range *rhs) { - EnsureRange(&lhs); - EnsureRange(&rhs); - return Truncate((int64_t)lhs->lower_ + (int64_t)rhs->lower_, - (int64_t)lhs->upper_ + (int64_t)rhs->upper_); + Range ret = Truncate((int64_t)lhs->lower_ + (int64_t)rhs->lower_, + (int64_t)lhs->upper_ + (int64_t)rhs->upper_); + return ret; } -Range * +Range Range::subTruncate(const Range *lhs, const Range *rhs) { - EnsureRange(&lhs); - EnsureRange(&rhs); - return Truncate((int64_t)lhs->lower_ - (int64_t)rhs->upper_, - (int64_t)lhs->upper_ - (int64_t)rhs->lower_); + Range ret = Truncate((int64_t)lhs->lower_ - (int64_t)rhs->upper_, + (int64_t)lhs->upper_ - (int64_t)rhs->lower_); + return ret; } -Range * +Range Range::and_(const Range *lhs, const Range *rhs) { - EnsureRange(&lhs); - EnsureRange(&rhs); - int64_t lower; int64_t upper; // If both numbers can be negative, result can be negative in the whole range if (lhs->lower_ < 0 && rhs->lower_ < 0) { lower = INT_MIN; upper = Max(lhs->upper_, rhs->upper_); - return new Range(lower, upper); + Range ret(lower, upper); + return ret; } // Only one of both numbers can be negative. // - result can't be negative // - Upper bound is minimum of both upper range, lower = 0; upper = Min(lhs->upper_, rhs->upper_); // EXCEPT when upper bound of non negative number is max value, // because negative value can return the whole max value. // -1 & 5 = 5 if (lhs->lower_ < 0) upper = rhs->upper_; if (rhs->lower_ < 0) upper = lhs->upper_; - return new Range(lower, upper); + Range ret(lower, upper); + return ret; + } - -Range * +Range Range::mul(const Range *lhs, const Range *rhs) { - EnsureRange(&lhs); - EnsureRange(&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 new Range( + Range ret( Min( Min(a, b), Min(c, d) ), Max( Max(a, b), Max(c, d) )); + return ret; } -Range * +Range Range::shl(const Range *lhs, int32 c) { - EnsureRange(&lhs); int32 shift = c & 0x1f; - return new Range( + Range ret( (int64_t)lhs->lower_ << shift, (int64_t)lhs->upper_ << shift); + return ret; } -Range * +Range Range::shr(const Range *lhs, int32 c) { - EnsureRange(&lhs); int32 shift = c & 0x1f; - return new Range( + Range ret( (int64_t)lhs->lower_ >> shift, (int64_t)lhs->upper_ >> shift); + return ret; } bool Range::precisionLossMul(const Range *lhs, const Range *rhs) { - EnsureRange(&lhs); - EnsureRange(&rhs); int64_t loss = 1LL<<53; // result must be lower than 2^53 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_; int64_t lower = Min( Min(a, b), Min(c, d) ); int64_t upper = Max( Max(a, b), Max(c, d) ); if (lower < 0) @@ -487,606 +468,88 @@ Range::update(const Range *other) lower_infinite_ = other->lower_infinite_; upper_ = other->upper_; upper_infinite_ = other->upper_infinite_; } return changed; } -/////////////////////////////////////////////////////////////////////////////// -// Range Computation for MIR Nodes -/////////////////////////////////////////////////////////////////////////////// - -void -MPhi::computeRange() -{ - if (type() != MIRType_Int32) - return; - - Range *range = NULL; - JS_ASSERT(getOperand(0)->op() != MDefinition::Op_OsrValue); - for (size_t i = 0; i < numOperands(); i++) { - if (getOperand(i)->block()->earlyAbort()) { - IonSpew(IonSpew_Range, "Ignoring unreachable input %d", getOperand(i)->id()); - continue; - } - - if (isOSRLikeValue(getOperand(i))) - continue; - - Range *input = getOperand(i)->range(); - - if (!input) { - range = NULL; - break; - } - - if (range) - range->unionWith(input); - else - range = new Range(*input); - } - - setRange(range); - - if (block()->isLoopHeader()) { - } -} - -void -MConstant::computeRange() -{ - if (type() == MIRType_Int32) - setRange(new Range(value().toInt32(), value().toInt32())); -} - -void -MCharCodeAt::computeRange() -{ - setRange(new Range(0, 65535)); //ECMA 262 says that the integer will be - //non-negative and at most 65535. -} - -void -MClampToUint8::computeRange() -{ - setRange(new Range(0, 255)); -} - -void -MBitAnd::computeRange() -{ - Range *left = getOperand(0)->range(); - Range *right = getOperand(1)->range(); - setRange(Range::and_(left, right)); -} - -void -MLsh::computeRange() -{ - MDefinition *right = getOperand(1); - if (!right->isConstant()) - return; - - int32 c = right->toConstant()->value().toInt32(); - const Range *other = getOperand(0)->range(); - setRange(Range::shl(other, c)); -} - -void -MRsh::computeRange() +static inline bool +AddToWorklist(MDefinitionVector &worklist, MDefinition *def) { - MDefinition *right = getOperand(1); - if (!right->isConstant()) - return; - - int32 c = right->toConstant()->value().toInt32(); - Range *other = getOperand(0)->range(); - setRange(Range::shr(other, c)); -} - -void -MAbs::computeRange() -{ - if (specialization_ != MIRType_Int32) - return; - - const Range *other = getOperand(0)->range(); - EnsureRange(&other); - - Range *range = new Range(0, - Max(Range::abs64((int64_t)other->lower()), - Range::abs64((int64_t)other->upper()))); - setRange(range); -} - -void -MAdd::computeRange() -{ - if (specialization() != MIRType_Int32) - return; - Range *left = getOperand(0)->range(); - Range *right = getOperand(1)->range(); - Range *next = isTruncated() ? Range::addTruncate(left,right) : Range::add(left, right); - setRange(next); -} - -void -MSub::computeRange() -{ - if (specialization() != MIRType_Int32) - return; - Range *left = getOperand(0)->range(); - Range *right = getOperand(1)->range(); - Range *next = isTruncated() ? Range::subTruncate(left,right) : Range::sub(left, right); - setRange(next); -} - -void -MMul::computeRange() -{ - if (specialization() != MIRType_Int32) - return; - Range *left = getOperand(0)->range(); - Range *right = getOperand(1)->range(); - if (isPossibleTruncated()) - implicitTruncate_ = !Range::precisionLossMul(left, right); - setRange(Range::mul(left, right)); -} - -void -MMod::computeRange() -{ - if (specialization() != MIRType_Int32) - return; - const Range *rhs = getOperand(1)->range(); - EnsureRange(&rhs); - int64_t a = Range::abs64((int64_t)rhs->lower()); - int64_t b = Range::abs64((int64_t)rhs->upper()); - if (a == 0 && b == 0) - return; - int64_t bound = Max(1-a, b-1); - setRange(new Range(-bound, bound)); -} - -/////////////////////////////////////////////////////////////////////////////// -// Range Analysis -/////////////////////////////////////////////////////////////////////////////// - -void -RangeAnalysis::markBlocksInLoopBody(MBasicBlock *header, MBasicBlock *current) -{ - // Visited. - current->mark(); - - // If we haven't reached the loop header yet, recursively explore predecessors - // if we haven't seen them already. - if (current != header) { - for (size_t i = 0; i < current->numPredecessors(); i++) { - if (current->getPredecessor(i)->isMarked()) - continue; - markBlocksInLoopBody(header, current->getPredecessor(i)); - } - } + if (def->isInWorklist()) + return true; + def->setInWorklist(); + return worklist.append(def); } -void -RangeAnalysis::analyzeLoop(MBasicBlock *header) -{ - // Try to compute an upper bound on the number of times the loop backedge - // will be taken. Look for tests that dominate the backedge and which have - // an edge leaving the loop body. - MBasicBlock *backedge = header->backedge(); - - // Ignore trivial infinite loops. - if (backedge == header) - return; - - markBlocksInLoopBody(header, backedge); - - LoopIterationBound *iterationBound = NULL; - - MBasicBlock *block = backedge; - do { - BranchDirection direction; - MTest *branch = block->immediateDominatorBranch(&direction); - - if (block == block->immediateDominator()) - break; - - block = block->immediateDominator(); - - if (branch) { - direction = NegateBranchDirection(direction); - MBasicBlock *otherBlock = branch->branchSuccessor(direction); - if (!otherBlock->isMarked()) { - iterationBound = - analyzeLoopIterationCount(header, branch, direction); - if (iterationBound) - break; - } - } - } while (block != header); - - if (!iterationBound) { - graph_.unmarkBlocks(); - return; - } - -#ifdef DEBUG - if (IonSpewEnabled(IonSpew_Range)) { - Sprinter sp(GetIonContext()->cx); - sp.init(); - iterationBound->sum.print(sp); - IonSpew(IonSpew_Range, "computed symbolic bound on backedges: %s", - sp.string()); - } -#endif - - // Try to compute symbolic bounds for the phi nodes at the head of this - // loop, expressed in terms of the iteration bound just computed. - - for (MDefinitionIterator iter(header); iter; iter++) { - MDefinition *def = *iter; - if (def->isPhi()) - analyzeLoopPhi(header, iterationBound, def->toPhi()); - } - - // Try to hoist any bounds checks from the loop using symbolic bounds. - - Vector<MBoundsCheck *, 0, IonAllocPolicy> hoistedChecks; - - for (ReversePostorderIterator iter(graph_.rpoBegin()); iter != graph_.rpoEnd(); iter++) { - MBasicBlock *block = *iter; - if (!block->isMarked()) - continue; - - for (MDefinitionIterator iter(block); iter; iter++) { - MDefinition *def = *iter; - if (def->isBoundsCheck() && def->isMovable()) { - if (tryHoistBoundsCheck(header, def->toBoundsCheck())) - hoistedChecks.append(def->toBoundsCheck()); - } - } - } - - // Note: replace all uses of the original bounds check with the - // actual index. This is usually done during bounds check elimination, - // but in this case it's safe to do it here since the load/store is - // definitely not loop-invariant, so we will never move it before - // one of the bounds checks we just added. - for (size_t i = 0; i < hoistedChecks.length(); i++) { - MBoundsCheck *ins = hoistedChecks[i]; - ins->replaceAllUsesWith(ins->index()); - ins->block()->discard(ins); - } - - graph_.unmarkBlocks(); -} - -LoopIterationBound * -RangeAnalysis::analyzeLoopIterationCount(MBasicBlock *header, - MTest *test, BranchDirection direction) +static inline MDefinition * +PopFromWorklist(MDefinitionVector &worklist) { - SimpleLinearSum lhs(NULL, 0); - MDefinition *rhs; - bool lessEqual; - if (!ExtractLinearInequality(test, direction, &lhs, &rhs, &lessEqual)) - return NULL; - - // Ensure the rhs is a loop invariant term. - if (rhs && rhs->block()->isMarked()) { - if (lhs.term && lhs.term->block()->isMarked()) - return NULL; - MDefinition *temp = lhs.term; - lhs.term = rhs; - rhs = temp; - if (!SafeSub(0, lhs.constant, &lhs.constant)) - return NULL; - lessEqual = !lessEqual; - } - - JS_ASSERT_IF(rhs, !rhs->block()->isMarked()); - - // Ensure the lhs is a phi node from the start of the loop body. - if (!lhs.term || !lhs.term->isPhi() || lhs.term->block() != header) - return NULL; - - // Check that the value of the lhs changes by a constant amount with each - // loop iteration. This requires that the lhs be written in every loop - // iteration with a value that is a constant difference from its value at - // the start of the iteration. - - if (lhs.term->toPhi()->numOperands() != 2) - return NULL; - - // The first operand of the phi should be the lhs' value at the start of - // the first executed iteration, and not a value written which could - // replace the second operand below during the middle of execution. - MDefinition *lhsInitial = lhs.term->toPhi()->getOperand(0); - if (lhsInitial->block()->isMarked()) - return NULL; - - // The second operand of the phi should be a value written by an add/sub - // in every loop iteration, i.e. in a block which dominates the backedge. - MDefinition *lhsWrite = lhs.term->toPhi()->getOperand(1); - if (lhsWrite->isBeta()) - lhsWrite = lhsWrite->getOperand(0); - if (!lhsWrite->isAdd() && !lhsWrite->isSub()) - return NULL; - if (!lhsWrite->block()->isMarked()) - return NULL; - MBasicBlock *bb = header->backedge(); - for (; bb != lhsWrite->block() && bb != header; bb = bb->immediateDominator()) {} - if (bb != lhsWrite->block()) - return NULL; - - SimpleLinearSum lhsModified = ExtractLinearSum(lhsWrite); - - // Check that the value of the lhs at the backedge is of the form - // 'old(lhs) + N'. We can be sure that old(lhs) is the value at the start - // of the iteration, and not that written to lhs in a previous iteration, - // as such a previous value could not appear directly in the addition: - // it could not be stored in lhs as the lhs add/sub executes in every - // iteration, and if it were stored in another variable its use here would - // be as an operand to a phi node for that variable. - if (lhsModified.term != lhs.term) - return NULL; - - LinearSum bound; - - if (lhsModified.constant == 1 && !lessEqual) { - // The value of lhs is 'initial(lhs) + iterCount' and this will end - // execution of the loop if 'lhs + lhsN >= rhs'. Thus, an upper bound - // on the number of backedges executed is: - // - // initial(lhs) + iterCount + lhsN == rhs - // iterCount == rhsN - initial(lhs) - lhsN - - if (rhs) - bound.add(rhs, 1); - bound.add(lhsInitial, -1); - - int32 lhsConstant; - if (!SafeSub(0, lhs.constant, &lhsConstant)) - return NULL; - bound.add(lhsConstant); - } else if (lhsModified.constant == -1 && lessEqual) { - // The value of lhs is 'initial(lhs) - iterCount'. Similar to the above - // case, an upper bound on the number of backedges executed is: - // - // initial(lhs) - iterCount + lhsN == rhs - // iterCount == initial(lhs) - rhs + lhsN - - bound.add(lhsInitial, 1); - if (rhs) - bound.add(rhs, -1); - bound.add(lhs.constant); - } else { - return NULL; - } - - return new LoopIterationBound(header, test, bound); -} - -void -RangeAnalysis::analyzeLoopPhi(MBasicBlock *header, LoopIterationBound *loopBound, MPhi *phi) -{ - // Given a bound on the number of backedges taken, compute an upper and - // lower bound for a phi node that may change by a constant amount each - // iteration. Unlike for the case when computing the iteration bound - // itself, the phi does not need to change the same amount every iteration, - // but is required to change at most N and be either nondecreasing or - // nonincreasing. - - if (phi->numOperands() != 2) - return; - - MBasicBlock *preLoop = header->loopPredecessor(); - JS_ASSERT(!preLoop->isMarked() && preLoop->successorWithPhis() == header); - - MBasicBlock *backedge = header->backedge(); - JS_ASSERT(backedge->isMarked() && backedge->successorWithPhis() == header); - - MDefinition *initial = phi->getOperand(preLoop->positionInPhiSuccessor()); - if (initial->block()->isMarked()) - return; - - SimpleLinearSum modified = ExtractLinearSum(phi->getOperand(backedge->positionInPhiSuccessor())); - - if (modified.term != phi || modified.constant == 0) - return; - - if (!phi->range()) - phi->setRange(new Range()); - - LinearSum initialSum; - initialSum.add(initial, 1); - - // The phi may change by N each iteration, and is either nondecreasing or - // nonincreasing. initial(phi) is either a lower or upper bound for the - // phi, and initial(phi) + loopBound * N is either an upper or lower bound, - // at all points within the loop, provided that loopBound >= 0. - // - // We are more interested, however, in the bound for phi at points - // dominated by the loop bound's test; if the test dominates e.g. a bounds - // check we want to hoist from the loop, using the value of the phi at the - // head of the loop for this will usually be too imprecise to hoist the - // check. These points will execute only if the backedge executes at least - // one more time (as the test passed and the test dominates the backedge), - // so we know both that loopBound >= 1 and that the phi's value has changed - // at most loopBound - 1 times. Thus, another upper or lower bound for the - // phi is initial(phi) + (loopBound - 1) * N, without requiring us to - // ensure that loopBound >= 0. - - LinearSum limitSum(loopBound->sum); - if (!limitSum.multiply(modified.constant) || !limitSum.add(initialSum)) - return; - - int32 negativeConstant; - if (!SafeSub(0, modified.constant, &negativeConstant) || !limitSum.add(negativeConstant)) - return; - - if (modified.constant > 0) { - phi->range()->setSymbolicLower(new SymbolicBound(NULL, initialSum)); - phi->range()->setSymbolicUpper(new SymbolicBound(loopBound, limitSum)); - } else { - phi->range()->setSymbolicUpper(new SymbolicBound(NULL, initialSum)); - phi->range()->setSymbolicLower(new SymbolicBound(loopBound, limitSum)); - } - - IonSpew(IonSpew_Range, "added symbolic range on %d", phi->id()); - SpewRange(phi); -} - -// Whether bound is valid at the specified bounds check instruction in a loop, -// and may be used to hoist ins. -static inline bool -SymbolicBoundIsValid(MBasicBlock *header, MBoundsCheck *ins, const SymbolicBound *bound) -{ - if (!bound->loop) - return true; - if (ins->block() == header) - return false; - MBasicBlock *bb = ins->block()->immediateDominator(); - while (bb != header && bb != bound->loop->test->block()) - bb = bb->immediateDominator(); - return bb == bound->loop->test->block(); -} - -// Convert all components of a linear sum *except* its constant to a definition, -// adding any necessary instructions to the end of block. -static inline MDefinition * -ConvertLinearSum(MBasicBlock *block, const LinearSum &sum) -{ - MDefinition *def = NULL; - - for (size_t i = 0; i < sum.numTerms(); i++) { - LinearTerm term = sum.term(i); - if (term.scale == 1) { - if (def) { - def = MAdd::New(def, term.term); - def->toAdd()->setInt32(); - block->insertBefore(block->lastIns(), def->toInstruction()); - } else { - def = term.term; - } - } else { - if (!def) { - def = MConstant::New(Int32Value(0)); - block->insertBefore(block->lastIns(), def->toInstruction()); - } - if (term.scale == -1) { - def = MSub::New(def, term.term); - def->toSub()->setInt32(); - block->insertBefore(block->lastIns(), def->toInstruction()); - } else { - MConstant *factor = MConstant::New(Int32Value(term.scale)); - block->insertBefore(block->lastIns(), factor); - MMul *mul = MMul::New(term.term, factor); - mul->setInt32(); - block->insertBefore(block->lastIns(), mul); - def = MAdd::New(def, mul); - block->insertBefore(block->lastIns(), def->toInstruction()); - } - } - } - - if (!def) { - def = MConstant::New(Int32Value(0)); - block->insertBefore(block->lastIns(), def->toInstruction()); - } - + JS_ASSERT(!worklist.empty()); + MDefinition *def = worklist.popCopy(); + def->setNotInWorklist(); return def; } -bool -RangeAnalysis::tryHoistBoundsCheck(MBasicBlock *header, MBoundsCheck *ins) -{ - // The bounds check's length must be loop invariant. - if (ins->length()->block()->isMarked()) - return false; - - // The bounds check's index should not be loop invariant (else we would - // already have hoisted it during LICM). - SimpleLinearSum index = ExtractLinearSum(ins->index()); - if (!index.term || !index.term->block()->isMarked()) - return false; - - // Check for a symbolic lower and upper bound on the index. If either - // condition depends on an iteration bound for the loop, only hoist if - // the bounds check is dominated by the iteration bound's test. - if (!index.term->range()) - return false; - const SymbolicBound *lower = index.term->range()->symbolicLower(); - if (!lower || !SymbolicBoundIsValid(header, ins, lower)) - return false; - const SymbolicBound *upper = index.term->range()->symbolicUpper(); - if (!upper || !SymbolicBoundIsValid(header, ins, upper)) - return false; - - MBasicBlock *preLoop = header->loopPredecessor(); - JS_ASSERT(!preLoop->isMarked()); - - MDefinition *lowerTerm = ConvertLinearSum(preLoop, lower->sum); - if (!lowerTerm) - return false; - - MDefinition *upperTerm = ConvertLinearSum(preLoop, upper->sum); - if (!upperTerm) - return false; - - // We are checking that index + indexConstant >= 0, and know that - // index >= lowerTerm + lowerConstant. Thus, check that: - // - // lowerTerm + lowerConstant + indexConstant >= 0 - // lowerTerm >= -lowerConstant - indexConstant - - int32 lowerConstant = 0; - if (!SafeSub(lowerConstant, index.constant, &lowerConstant)) - return false; - if (!SafeSub(lowerConstant, lower->sum.constant(), &lowerConstant)) - return false; - MBoundsCheckLower *lowerCheck = MBoundsCheckLower::New(lowerTerm); - lowerCheck->setMinimum(lowerConstant); - - // We are checking that index < boundsLength, and know that - // index <= upperTerm + upperConstant. Thus, check that: - // - // upperTerm + upperConstant < boundsLength - - int32 upperConstant = index.constant; - if (!SafeAdd(upper->sum.constant(), upperConstant, &upperConstant)) - return false; - MBoundsCheck *upperCheck = MBoundsCheck::New(upperTerm, ins->length()); - upperCheck->setMinimum(upperConstant); - upperCheck->setMaximum(upperConstant); - - // Hoist the loop invariant upper and lower bounds checks. - preLoop->insertBefore(preLoop->lastIns(), lowerCheck); - preLoop->insertBefore(preLoop->lastIns(), upperCheck); - - return true; -} bool RangeAnalysis::analyze() { - IonSpew(IonSpew_Range, "Doing range propagation"); + int numBlocks = 0; + for (PostorderIterator i(graph_.poBegin()); i != graph_.poEnd(); i++) { + numBlocks++; + MBasicBlock *curBlock = *i; + if (!curBlock->isLoopHeader()) + continue; + for (MPhiIterator pi(curBlock->phisBegin()); pi != curBlock->phisEnd(); pi++) + if (!pi->initCounts()) + return false; + } - for (ReversePostorderIterator iter(graph_.rpoBegin()); iter != graph_.rpoEnd(); iter++) { - MBasicBlock *block = *iter; + IonSpew(IonSpew_Range, "Doing range propagation"); + MDefinitionVector worklist; - for (MDefinitionIterator iter(block); iter; iter++) { + for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) { + for (MDefinitionIterator iter(*block); iter; iter++) { MDefinition *def = *iter; - def->computeRange(); - IonSpew(IonSpew_Range, "computing range on %d", def->id()); - SpewRange(def); + AddToWorklist(worklist, def); + } + } + size_t iters = 0; - if (block->isLoopHeader()) - analyzeLoop(block); + while (!worklist.empty()) { + MDefinition *def = PopFromWorklist(worklist); + IonSpew(IonSpew_Range, "recomputing range on %d", def->id()); + SpewRange(def); + if (!def->earlyAbortCheck() && def->recomputeRange()) { + JS_ASSERT(def->range()->lower() <= def->range()->upper()); + IonSpew(IonSpew_Range, "Range changed; adding consumers"); + IonSpew(IonSpew_Range, "New range for %d is: (%d, %d)", def->id(), def->range()->lower(), def->range()->upper()); + for (MUseDefIterator use(def); use; use++) { + if(!AddToWorklist(worklist, use.def())) + return false; + } + } + iters++; + if (iters >= numBlocks * 100) + return false; } + // Cleanup (in case we stopped due to MAX_ITERS) + for(size_t i = 0; i < worklist.length(); i++) + worklist[i]->setNotInWorklist(); + +#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; }
--- a/js/src/ion/RangeAnalysis.h +++ b/js/src/ion/RangeAnalysis.h @@ -6,99 +6,48 @@ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ #ifndef jsion_range_analysis_h__ #define jsion_range_analysis_h__ #include "wtf/Platform.h" #include "MIR.h" #include "CompileInfo.h" -#include "IonAnalysis.h" namespace js { namespace ion { class MBasicBlock; class MIRGraph; -// An upper bound computed on the number of backedges a loop will take. -// This count only includes backedges taken while running Ion code: for OSR -// loops, this will exclude iterations that executed in the interpreter or in -// baseline compiled code. -struct LoopIterationBound : public TempObject -{ - // Loop for which this bound applies. - MBasicBlock *header; - - // Test from which this bound was derived. Code in the loop body which this - // test dominates (will include the backedge) will execute at most 'bound' - // times. Other code in the loop will execute at most '1 + Max(bound, 0)' - // times. - MTest *test; - - // Symbolic bound computed for the number of backedge executions. - LinearSum sum; - - LoopIterationBound(MBasicBlock *header, MTest *test, LinearSum sum) - : header(header), test(test), sum(sum) - { - } -}; - -// A symbolic upper or lower bound computed for a term. -struct SymbolicBound : public TempObject -{ - // Any loop iteration bound from which this was derived. - // - // If non-NULL, then 'sum' is only valid within the loop body, at points - // dominated by the loop bound's test (see LoopIterationBound). - // - // If NULL, then 'sum' is always valid. - LoopIterationBound *loop; - - // Computed symbolic bound, see above. - LinearSum sum; - - SymbolicBound(LoopIterationBound *loop, LinearSum sum) - : loop(loop), sum(sum) - { - } - - void print(Sprinter &sp) const; -}; - 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(); - - private: - void analyzeLoop(MBasicBlock *header); - LoopIterationBound *analyzeLoopIterationCount(MBasicBlock *header, - MTest *test, BranchDirection direction); - void analyzeLoopPhi(MBasicBlock *header, LoopIterationBound *loopBound, MPhi *phi); - bool tryHoistBoundsCheck(MBasicBlock *header, MBoundsCheck *ins); - void markBlocksInLoopBody(MBasicBlock *header, MBasicBlock *current); }; -class Range : public TempObject { +struct RangeChangeCount; +class Range { private: - // Absolute ranges. - // + // :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. @@ -115,77 +64,72 @@ class Range : public TempObject { // 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_; - // Any symbolic lower or upper bound computed for this term. - const SymbolicBound *symbolicLower_; - const SymbolicBound *symbolicUpper_; - public: Range() : lower_(JSVAL_INT_MIN), lower_infinite_(true), upper_(JSVAL_INT_MAX), - upper_infinite_(true), - symbolicLower_(NULL), - symbolicUpper_(NULL) + upper_infinite_(true) {} - Range(int64_t l, int64_t h) - : symbolicLower_(NULL), - symbolicUpper_(NULL) - { + Range(int64_t l, int64_t h) { setLower(l); setUpper(h); } Range(const Range &other) - : lower_(other.lower_), - lower_infinite_(other.lower_infinite_), - upper_(other.upper_), - upper_infinite_(other.upper_infinite_), - symbolicLower_(NULL), - symbolicUpper_(NULL) + : lower_(other.lower_), + lower_infinite_(other.lower_infinite_), + upper_(other.upper_), + upper_infinite_(other.upper_infinite_) {} - - static Range *Truncate(int64_t l, int64_t h); + static Range Truncate(int64_t l, int64_t h) { + Range ret(l,h); + if (!ret.isFinite()) { + ret.makeLowerInfinite(); + ret.makeUpperInfinite(); + } + return ret; + } static int64_t abs64(int64_t x) { #ifdef WTF_OS_WINDOWS return _abs64(x); #else return llabs(x); #endif } - void print(Sprinter &sp) const; + 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, bool *emptyRange); - static Range * addTruncate(const Range *lhs, const Range *rhs); - static Range * subTruncate(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 * and_(const Range *lhs, const Range *rhs); - static Range * shl(const Range *lhs, int32 c); - static Range * shr(const Range *lhs, int32 c); + static Range intersect(const Range *lhs, const Range *rhs, bool *nullRange); + static Range addTruncate(const Range *lhs, const Range *rhs); + static Range subTruncate(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 and_(const Range *lhs, const Range *rhs); + static Range shl(const Range *lhs, int32 c); + static Range shr(const Range *lhs, int32 c); static bool precisionLossMul(const Range *lhs, const Range *rhs); inline void makeLowerInfinite() { lower_infinite_ = true; lower_ = JSVAL_INT_MIN; } inline void makeUpperInfinite() { @@ -235,29 +179,44 @@ class Range : public TempObject { upper_ = (int32)x; upper_infinite_ = false; } } void set(int64_t l, int64_t h) { setLower(l); setUpper(h); } +}; - const SymbolicBound *symbolicLower() const { - return symbolicLower_; - } - const SymbolicBound *symbolicUpper() const { - return symbolicUpper_; +struct RangeChangeCount { + Range oldRange; + unsigned char lowerCount_ : 4; + unsigned char upperCount_ : 4; + RangeChangeCount() : oldRange(), lowerCount_(0), upperCount_(0) {}; + void updateRange(Range *newRange) { + JS_ASSERT(newRange->lower() >= oldRange.lower()); + if (newRange->lower() != oldRange.lower()) + lowerCount_ = lowerCount_ < 15 ? lowerCount_ + 1 : lowerCount_; + JS_ASSERT(newRange->upper() <= oldRange.upper()); + if (newRange->upper() != oldRange.upper()) + upperCount_ = upperCount_ < 15 ? upperCount_ + 1 : upperCount_; + oldRange = *newRange; } - - void setSymbolicLower(SymbolicBound *bound) { - symbolicLower_ = bound; - } - void setSymbolicUpper(SymbolicBound *bound) { - symbolicUpper_ = bound; - } +}; +class RangeUpdater { + Range r_; + bool lowerSet_; + bool upperSet_; + public: + RangeUpdater() : r_(), lowerSet_(false), upperSet_(false) {} + void unionWith(const Range *other); + void unionWith(RangeChangeCount *other); + void updateLower(const Range * other); + void updateUpper(const Range * other); + Range *getRange() { JS_ASSERT(lowerSet_ && upperSet_); return &r_; } + void printRange(FILE *fp) { r_.printRange(fp); } }; } // namespace ion } // namespace js #endif // jsion_range_analysis_h__