| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (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.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| /** |
| * @author Evgueni Brevnov |
| * |
| */ |
| |
| #include <stdlib.h> |
| |
| #include "dabce.h" |
| #include "optpass.h" |
| #include "FlowGraph.h" |
| |
| namespace Jitrino { |
| |
| DEFINE_SESSION_ACTION(DynamicABCEPass, dabce, "Dynamic elimination of array bound checks") |
| |
| void DynamicABCEPass::_run(IRManager& irm) { |
| |
| DynamicABCE dynamicABCE(irm, this); |
| dynamicABCE.run(); |
| } |
| |
| DynamicABCE::DynamicABCE(IRManager& irm, SessionAction* sa) : |
| INC_SEQ_PROB(0.8), IN_BOUNDS_PROB(0.9), |
| irManager(irm), memoryManager(irm.getMemoryManager()), |
| flowGraph(irm.getFlowGraph()), typeManager(irm.getTypeManager()), |
| instFactory(irm.getInstFactory()), opndManager (irm.getOpndManager()), |
| arrayAccesses(memoryManager), inductionInfo(memoryManager), |
| eliminationInfo(memoryManager), monotonicityInfo(memoryManager), |
| loopsToOptimize(memoryManager), flags(*irm.getOptimizerFlags().dabceFlags) { |
| |
| // Build dominators. |
| OptPass::computeDominatorsAndLoops(irManager, true); |
| dce = new (memoryManager) DeadCodeEliminator(irManager); |
| sortByHotness = new (memoryManager) HotnessSorter; |
| loopTree = irm.getLoopTree(); |
| } |
| |
| void DynamicABCE::readFlags(Action* argSource, DynamicABCEFlags* flags) { |
| flags->sizeThreshold = argSource->getIntArg("dabce.sizeThreshold", 1); |
| flags->hotnessThreshold = argSource->getIntArg("dabce.hotnessThreshold", 1); |
| } |
| |
| void DynamicABCE::showFlags(std::ostream& os) { |
| os << " Dynamic ABCE flags:" << std::endl; |
| os << " dabce.sizeThreshold - maximum number of nodes in loop" << std::endl; |
| os << " dabce.hotnessThreshold - minimum hotness of loop header " << std::endl; |
| } |
| |
| void DynamicABCE::run() { |
| assert(loopTree->isValid()); |
| |
| // No loops, nothing to optimize. |
| if (!loopTree->hasLoops()) return; |
| |
| LoopNode* topLevelLoop = (LoopNode*)loopTree->getRoot(); |
| |
| // Find all loops. |
| findLoopsToOptimize(topLevelLoop); |
| |
| // Sort loops by hotness. |
| std::sort(loopsToOptimize.begin(), loopsToOptimize.end(), *sortByHotness); |
| |
| // Optimize found loops. |
| optimizeLoops(); |
| } |
| |
| void DynamicABCE::findLoopsToOptimize(LoopNode* topLevelLoop) { |
| LoopNode* innerLoop; |
| |
| if (topLevelLoop->getHeader() != NULL) { |
| loopsToOptimize.push_back(topLevelLoop->getHeader()); |
| } |
| for (innerLoop = topLevelLoop->getChild(); innerLoop != NULL; |
| innerLoop = innerLoop->getSiblings()) { |
| findLoopsToOptimize(innerLoop); |
| } |
| } |
| |
| void DynamicABCE::optimizeLoops() { |
| InductionDetector* inductionDetector = NULL; |
| Node* loopHeader = NULL; |
| StlVector<Node*>::iterator loopIt; |
| ArrayAccessInfo::iterator accessIt; |
| |
| // Apply transformation from top level to inner most loops. |
| while (!loopsToOptimize.empty()) { |
| clearAll(); |
| |
| loopIt = loopsToOptimize.begin(); |
| loopHeader = *loopIt; |
| loopsToOptimize.erase(loopIt); |
| |
| |
| optimizedLoop = loopTree->getLoopNode(loopHeader, false); |
| assert(optimizedLoop != NULL); |
| |
| if (Log::isEnabled()) { |
| Log::out() << "Optimizing loop " << loopHeader->getId() << std::endl; |
| |
| } |
| |
| double relativeHotness = loopHeader->getExecCount() / flowGraph.getEntryNode()->getExecCount(); |
| |
| if (relativeHotness < flags.hotnessThreshold) { |
| if (Log::isEnabled()) { |
| Log::out() << "FAILED: Loop is too cold.\n"; |
| } |
| // No need to traverse other loops. They are even colder. |
| break; |
| } |
| |
| if (optimizedLoop->getNodesInLoop().size() > relativeHotness * flags.sizeThreshold) { |
| if (Log::isEnabled()) { |
| Log::out() << "FAILED: Loop is too large.\n"; |
| } |
| continue; |
| } |
| |
| // Find candidates for elimintation. |
| findArrayAccesses(); |
| |
| // Check if we found at least one candidate for elimination. |
| if (Log::isEnabled() && arrayAccesses.empty()) { |
| Log::out() << "FAILED: No bound checks found.\n"; |
| } |
| |
| inductionDetector = InductionDetector::create(memoryManager, optimizedLoop); |
| |
| while (!arrayAccesses.empty()) { |
| accessIt = arrayAccesses.begin(); |
| const ArrayAccessTemplate& arrayAccess = **accessIt; |
| arrayAccesses.erase(accessIt); |
| |
| eliminateBoundsCheck(inductionDetector, arrayAccess); |
| |
| // Loop tree can be updated so reload related info. |
| if (optimizedLoop != loopTree->getLoopNode(loopHeader, false)) { |
| optimizedLoop = loopTree->getLoopNode(loopHeader, false); |
| inductionDetector = InductionDetector::create(memoryManager, optimizedLoop); |
| findArrayAccesses(); |
| } |
| } |
| } |
| } |
| |
| bool DynamicABCE::eliminateBoundsCheck(InductionDetector* inductionDetector, |
| const ArrayAccessTemplate& arrayAccess) { |
| InductiveOpndLoopInfo* inductionInfo = NULL; |
| InductiveOpndLoopInfo* base = NULL; |
| InvariantOpndLoopInfo* scale = NULL; |
| InvariantOpndLoopInfo* stride = NULL; |
| InvariantOpndLoopInfo* start = NULL; |
| InvariantOpndLoopInfo* end = NULL; |
| IndexEliminationInfo* indexElimintaionInfo = NULL; |
| bool canReachBound = false; |
| bool result = false; |
| |
| indexElimintaionInfo = eliminationInfo[arrayAccess.array]; |
| |
| if (indexElimintaionInfo == NULL) { |
| indexElimintaionInfo = new (memoryManager) IndexEliminationInfo(memoryManager); |
| eliminationInfo[arrayAccess.array] = indexElimintaionInfo; |
| } else { |
| if (indexElimintaionInfo->has(arrayAccess.index)) { |
| // Constraints already generated. Just remove bounds check. |
| instFactory.makeTauSafe(arrayAccess.checkBoundsInst->getDst())-> |
| insertAfter(arrayAccess.checkBoundsInst); |
| arrayAccess.checkBoundsInst->unlink(); |
| result = true; |
| |
| if (Log::isEnabled()) { |
| Log::out() << "SUCCEED: Array bound check "; |
| arrayAccess.checkBoundsInst->print(Log::out()); |
| Log::out() << " was removed.\n"; |
| } |
| } |
| return result; |
| } |
| |
| // Check that array reference and array lengh defined out of the loop. |
| if (isDefInLoop(arrayAccess.array) || isDefInLoop(arrayAccess.arrayLen)) { |
| if (Log::isEnabled()) { |
| Log::out() << "FAILED: Array "; |
| arrayAccess.array->print(Log::out()); |
| Log::out() << " is not loop invariant.\n"; |
| } |
| goto done; |
| } |
| |
| // Create initial subgraph structure. |
| subGraph = new (memoryManager) SubGraph(memoryManager); |
| subGraph->setEntryNode(subGraph->createBlockNode(instFactory.makeLabel())); |
| subGraph->setExitNode(subGraph->createBlockNode(instFactory.makeLabel())); |
| subGraph->setSpecialExitNode(subGraph->createBlockNode(instFactory.makeLabel())); |
| subGraph->addEdge(subGraph->getEntryNode(), subGraph->getExitNode()); |
| |
| |
| inductionInfo = getSimplifiedInduction(inductionDetector, arrayAccess); |
| |
| if (inductionInfo == NULL) { |
| if (Log::isEnabled()) { |
| Log::out() << "FAILED: Index "; |
| arrayAccess.index->print(Log::out()); |
| Log::out() << " is not loop inductive variable.\n"; |
| } |
| goto done; |
| } |
| |
| base = inductionInfo->getBase(); |
| assert(base->getOpnd() == base->getBase()->getOpnd()); |
| start = base->getStartValue(); |
| end = base->getEndValue(); |
| |
| // start and end values should be detected as loop invariants... |
| if (start == NULL || end == NULL) { |
| if (Log::isEnabled()) { |
| Log::out() << "FAILED: start/end value is not loop invariant.\n"; |
| } |
| goto done; |
| } |
| |
| // ... and should be defined out of the loop. |
| if (isDefInLoop(start->getOpnd()) || isDefInLoop(end->getOpnd())) { |
| if (Log::isEnabled()) { |
| Log::out() << "FAILED: start/end value has loop scope.\n"; |
| } |
| goto done; |
| } |
| |
| // Promote start/end value from variable to temporary. |
| start = promoteVarToTmp(start, inductionDetector); |
| end = promoteVarToTmp(end, inductionDetector); |
| base->setStartValue(start); |
| base->setEndValue(end); |
| |
| if (!isProperMonotonicity(base, start, end)) { |
| if (Log::isEnabled()) { |
| Log::out() << "FAILED: Wrong monotonicity.\n"; |
| } |
| goto done; |
| } |
| |
| if (inductionInfo != base) { |
| scale = inductionInfo->getScale(); |
| stride = inductionInfo->getStride(); |
| } |
| |
| canReachBound = base->getBoundType() == LOW_EQ_BOUND || |
| base->getBoundType() == UPPER_EQ_BOUND; |
| // Generate constraint for initial value. |
| genBoundConstraint(scale, start, stride, arrayAccess.arrayLen, true); |
| // Generate constraint for final value. |
| genBoundConstraint(scale, end, stride, arrayAccess.arrayLen, canReachBound); |
| // Link subGraph node. |
| linkSubGraph(); |
| // Remove bounds check. |
| instFactory.makeTauSafe(arrayAccess.checkBoundsInst->getDst())-> |
| insertAfter(arrayAccess.checkBoundsInst); |
| arrayAccess.checkBoundsInst->unlink(); |
| |
| if (Log::isEnabled()) { |
| Log::out() << "SUCCEED: Array bound check "; |
| arrayAccess.checkBoundsInst->print(Log::out()); |
| Log::out() << " was removed.\n"; |
| } |
| |
| result = true; |
| done: |
| (*indexElimintaionInfo)[arrayAccess.index] = result; |
| return result; |
| } |
| |
| InvariantOpndLoopInfo* |
| DynamicABCE::promoteVarToTmp(InvariantOpndLoopInfo* invOpnd, |
| InductionDetector* inductionDetector) { |
| SsaOpnd* tmpOpnd = NULL; |
| SsaVarOpnd* varOpnd = NULL; |
| |
| if (!invOpnd->getOpnd()->isSsaVarOpnd()) { |
| return invOpnd; |
| } |
| |
| varOpnd = invOpnd->getOpnd()->asSsaVarOpnd(); |
| |
| if (varOpnd->getInst()->isStVar()) { |
| tmpOpnd = varOpnd->getInst()->getSrc(0)->asSsaTmpOpnd(); |
| } else { |
| tmpOpnd = opndManager.createSsaTmpOpnd(varOpnd->getType()); |
| subGraph->getEntryNode()->appendInst(instFactory.makeLdVar(tmpOpnd, varOpnd)); |
| } |
| |
| return inductionDetector->createInvariantOpnd(tmpOpnd); |
| } |
| |
| InductiveOpndLoopInfo* |
| DynamicABCE::getSimplifiedInduction(InductionDetector* inductionDetector, |
| const ArrayAccessTemplate& arrayAccess) { |
| SsaOpnd* complexScale = NULL; |
| SsaOpnd* complexStride = NULL; |
| Modifier mulMod = Modifier(Overflow_None) | Modifier(Exception_Never); |
| Modifier addMod = mulMod | Modifier(Strict_No); |
| Node* subGraphEnter = NULL; |
| OpndLoopInfo* opndLoopInfo = NULL; |
| InvariantOpndLoopInfo* scale = NULL; |
| InductiveOpndLoopInfo* base = NULL; |
| InvariantOpndLoopInfo* stride = NULL; |
| InductiveOpndLoopInfo* indexInfo = NULL; |
| InductiveOpndLoopInfo* simplifiedInductionInfo = NULL; |
| |
| |
| if (inductionInfo.has(arrayAccess.index)) { |
| return inductionInfo[arrayAccess.index]; |
| } |
| |
| opndLoopInfo = inductionDetector->getOpndInfo(arrayAccess.index); |
| |
| if (opndLoopInfo == NULL || !opndLoopInfo->isInductive()) { |
| goto done; |
| } |
| |
| indexInfo = opndLoopInfo->asInductive(); |
| scale = indexInfo->getScale(); |
| stride = indexInfo->getStride(); |
| subGraphEnter = subGraph->getEntryNode(); |
| |
| // Scale and sride must be defined out of the loop. |
| if (isDefInLoop(scale->getOpnd()) || isDefInLoop(stride->getOpnd())) { |
| goto done; |
| } |
| |
| // Check if its already simple induction. |
| if (indexInfo == indexInfo->getBase()) { |
| simplifiedInductionInfo = indexInfo; |
| goto done; |
| } |
| |
| do { |
| SsaOpnd* tmpOpnd1 = NULL; |
| SsaOpnd* tmpOpnd2 = NULL; |
| |
| scale = indexInfo->getScale(); |
| base = indexInfo->getBase(); |
| stride = indexInfo->getStride(); |
| |
| assert(scale != NULL && base != NULL && stride != NULL); |
| |
| if (isDefInLoop(scale->getOpnd()) || isDefInLoop(stride->getOpnd())) { |
| goto done; |
| } |
| |
| if (complexStride == NULL) { |
| complexStride = stride->getOpnd(); |
| } else if (!stride->isConstant() || stride->asConstant()->getValue() != 0) { |
| if (complexScale != NULL) { |
| tmpOpnd1 = opndManager.createSsaTmpOpnd(complexScale->getType()); |
| subGraphEnter->appendInst(instFactory.makeMul(mulMod, tmpOpnd1, complexScale, stride->getOpnd())); |
| } else { |
| tmpOpnd1 = stride->getOpnd(); |
| } |
| tmpOpnd2 = opndManager.createSsaTmpOpnd(complexStride->getType()); |
| subGraphEnter->appendInst(instFactory.makeAdd(addMod, tmpOpnd2, complexStride, tmpOpnd1)); |
| complexStride = tmpOpnd2; |
| } |
| |
| if (complexScale == NULL) { |
| complexScale = scale->getOpnd(); |
| } else if (!scale->isConstant() || scale->asConstant()->getValue() != 1) { |
| tmpOpnd1 = opndManager.createSsaTmpOpnd(complexScale->getType()); |
| subGraphEnter->appendInst(instFactory.makeMul(mulMod, tmpOpnd1, complexScale, scale->getOpnd())); |
| complexScale = tmpOpnd1; |
| } |
| |
| } while (indexInfo != base && |
| (indexInfo = inductionDetector->getOpndInfo(base->getOpnd())->asInductive()) != NULL); |
| |
| scale = complexScale ? inductionDetector->createInvariantOpnd(complexScale) : NULL; |
| stride = complexStride ? inductionDetector->createInvariantOpnd(complexStride) : NULL; |
| simplifiedInductionInfo = |
| inductionDetector->createInductiveOpnd(arrayAccess.index, scale, base, stride); |
| done: |
| inductionInfo[arrayAccess.index] = simplifiedInductionInfo; |
| return simplifiedInductionInfo; |
| } |
| |
| bool DynamicABCE::isProperMonotonicity(InductiveOpndLoopInfo* base, |
| InvariantOpndLoopInfo* startValue, |
| InvariantOpndLoopInfo* endValue) { |
| Modifier aluMod; |
| Type* int32Type; |
| VarOpnd* fk; |
| Node* startNode = NULL; |
| Node* subGraphExit = NULL; |
| Node* increasingNode = NULL; |
| Node* decreasingNode = NULL; |
| InvariantOpndLoopInfo* scale; |
| InvariantOpndLoopInfo* stride; |
| bool isScaleEqualOne = false; |
| bool isStrideEqualZero = false; |
| bool result = false; |
| |
| assert(base->getOpnd() == base->getBase()->getOpnd()); |
| |
| if (monotonicityInfo.has(base->getOpnd())) { |
| return monotonicityInfo[base->getOpnd()]; |
| } |
| |
| aluMod = Modifier(Overflow_None) | Modifier(Exception_Never) | Modifier(Strict_No); |
| int32Type = typeManager.getInt32Type(); |
| subGraphExit = subGraph->getExitNode(); |
| |
| // Generate bound values check. |
| switch (base->getBoundType()) { |
| case LOW_BOUND: |
| case LOW_EQ_BOUND: |
| increasingNode = subGraph->getSpecialExitNode(); |
| if (startValue->isConstant() && endValue->isConstant() && |
| startValue->asConstant()->getValue() >= endValue->asConstant()->getValue()) { |
| decreasingNode = subGraphExit; |
| } else { |
| decreasingNode = subGraph->createBlockNode(instFactory.makeLabel()); |
| subGraph->addEdge(decreasingNode, subGraph->getSpecialExitNode(), 0.1); |
| subGraph->addEdge(decreasingNode, subGraphExit, 0.9); |
| decreasingNode->appendInst(instFactory.makeBranch(Cmp_GTE, |
| int32Type->tag, startValue->getOpnd(), endValue->getOpnd(), |
| ((Inst*)subGraphExit->getLabelInst())->asLabelInst())); |
| } |
| break; |
| case UPPER_BOUND: |
| case UPPER_EQ_BOUND: |
| decreasingNode = subGraph->getSpecialExitNode(); |
| if (startValue->isConstant() && endValue->isConstant() && |
| startValue->asConstant()->getValue() <= endValue->asConstant()->getValue()) { |
| increasingNode = subGraphExit; |
| } else { |
| increasingNode = subGraph->createBlockNode(instFactory.makeLabel()); |
| subGraph->addEdge(increasingNode, subGraph->getSpecialExitNode(), 0.1); |
| subGraph->addEdge(increasingNode, subGraphExit, 0.9); |
| increasingNode->appendInst(instFactory.makeBranch(Cmp_GTE, |
| int32Type->tag, endValue->getOpnd(), startValue->getOpnd(), |
| ((Inst*)subGraphExit->getLabelInst())->asLabelInst())); |
| } |
| break; |
| default: |
| goto done; |
| } |
| |
| // Generate monotonicity check. |
| fk = opndManager.createVarOpnd(int32Type, false); |
| scale = base->getScale(); |
| stride = base->getStride(); |
| |
| isScaleEqualOne = (scale->isConstant() && scale->asConstant()->getValue() == 1); |
| // If scale is equal to one it doesn't affect direction of monotonicity. |
| if (!isScaleEqualOne) { |
| startNode = subGraph->createBlockNode(instFactory.makeLabel()); |
| Node* monCheckNode = flowGraph.createBlockNode(instFactory.makeLabel()); |
| SsaOpnd* one = opndManager.createSsaTmpOpnd(int32Type); |
| SsaOpnd* tk = opndManager.createSsaTmpOpnd(int32Type); |
| startNode->appendInst(instFactory.makeLdConst(one, 1)); |
| startNode->appendInst(instFactory.makeSub(aluMod, tk, scale->getOpnd(), one)); |
| |
| Node* trueNode = subGraph->createBlockNode(instFactory.makeLabel()); |
| Node* falseNode = subGraph->createBlockNode(instFactory.makeLabel()); |
| |
| subGraph->addEdge(startNode, trueNode, 0.5); |
| subGraph->addEdge(trueNode, monCheckNode, 1.0); |
| subGraph->addEdge(startNode, falseNode, 0.5); |
| |
| startNode->appendInst(instFactory.makeBranch(Cmp_Zero, int32Type->tag, |
| tk, ((Inst*)trueNode->getLabelInst())->asLabelInst())); |
| |
| // Generate true node instructions. |
| SsaOpnd* strideOpnd = stride->getOpnd(); |
| if (strideOpnd == NULL) { |
| strideOpnd = opndManager.createSsaTmpOpnd(int32Type); |
| trueNode->appendInst(instFactory.makeLdConst(strideOpnd, |
| stride->asConstant()->getValue())); |
| } |
| trueNode->appendInst(instFactory.makeStVar(fk, strideOpnd)); |
| |
| // Generate false node instructions. |
| isStrideEqualZero = (stride->isConstant()&& |
| stride->asConstant()->getValue() == 0); |
| SsaTmpOpnd* rk = opndManager.createSsaTmpOpnd(int32Type); |
| if (!isStrideEqualZero) { |
| SsaTmpOpnd* tauSafe = opndManager.createSsaTmpOpnd(typeManager.getTauType()); |
| SsaTmpOpnd* div = opndManager.createSsaTmpOpnd(typeManager.getFloatType()); |
| falseNode->appendInst(instFactory.makeTauSafe(tauSafe)); |
| falseNode->appendInst(instFactory.makeTauDiv(aluMod, div, |
| stride->getOpnd(), tk, tauSafe)); |
| falseNode->appendInst(instFactory.makeAdd(aluMod, rk, |
| startValue->getOpnd(), div)); |
| } else { |
| falseNode->appendInst(instFactory.makeCopy(rk, startValue->getOpnd())); |
| } |
| |
| Node* subTrueNode = subGraph->createBlockNode(instFactory.makeLabel()); |
| Node* subFalseNode = subGraph->createBlockNode(instFactory.makeLabel()); |
| |
| subGraph->addEdge(falseNode, subTrueNode, 0.5); |
| subGraph->addEdge(falseNode, subFalseNode, 0.5); |
| subGraph->addEdge(subTrueNode, monCheckNode, 1.0); |
| subGraph->addEdge(subFalseNode, monCheckNode, 1.0); |
| |
| falseNode->appendInst(instFactory.makeBranch(Cmp_GT, int32Type->tag, |
| tk, ((Inst*)subTrueNode->getLabelInst())->asLabelInst())); |
| |
| // Generate true subnode instructions. |
| trueNode->appendInst(instFactory.makeStVar(fk, rk)); |
| |
| // Generate false subnode instructions. |
| SsaTmpOpnd* negrk = opndManager.createSsaTmpOpnd(int32Type); |
| falseNode->appendInst(instFactory.makeNeg(negrk, rk)); |
| falseNode->appendInst(instFactory.makeStVar(fk, negrk)); |
| |
| // Generate final check. |
| SsaTmpOpnd* checkOpnd = opndManager.createSsaTmpOpnd(int32Type); |
| monCheckNode->appendInst(instFactory.makeLdVar(checkOpnd, fk)); |
| monCheckNode->appendInst(instFactory.makeBranch(Cmp_GTE, |
| int32Type->tag, checkOpnd, ((Inst*)increasingNode->getLabelInst())->asLabelInst())); |
| // Link monotonicity check to bounds check nodes. |
| subGraph->addEdge(monCheckNode, increasingNode, INC_SEQ_PROB); |
| subGraph->addEdge(monCheckNode, decreasingNode, 1 - INC_SEQ_PROB); |
| } else { |
| if (!stride->isConstant()) { |
| // Generate runtime check. |
| startNode = flowGraph.createBlockNode(instFactory.makeLabel()); |
| startNode->appendInst(instFactory.makeBranch(Cmp_GTE, int32Type->tag, |
| stride->getOpnd(), ((Inst*)increasingNode->getLabelInst())->asLabelInst())); |
| subGraph->addEdge(startNode, increasingNode, INC_SEQ_PROB); |
| subGraph->addEdge(startNode, decreasingNode, 1 - INC_SEQ_PROB); |
| } else { |
| // Scale is equal to 1 here => only stride determines direction of monotonicity. |
| if (stride->asConstant()->getValue() >= 0) { |
| // That's not an inductive variable/ |
| assert(stride->asConstant()->getValue() != 0); |
| // Increasing sequence. |
| if (base->getBoundType() == UPPER_BOUND || base->getBoundType() == UPPER_EQ_BOUND) { |
| startNode = increasingNode; |
| } else { |
| goto done; |
| } |
| } else { |
| assert(stride->asConstant()->getValue() < 0); |
| // Decreasing sequence. |
| if (base->getBoundType() == LOW_BOUND || base->getBoundType() == LOW_EQ_BOUND) { |
| startNode = decreasingNode; |
| } else { |
| goto done; |
| } |
| } |
| } |
| } |
| // Link monotonicity check. |
| if (startNode != NULL) { |
| // Remove link between enter & exit nodes. |
| Node* subGraphEnter = subGraph->getEntryNode(); |
| Edge* edge = subGraphEnter->findEdge(true, subGraphExit); |
| if (edge != NULL) { |
| subGraph->removeEdge(edge); |
| } |
| subGraph->addEdge(subGraphEnter, startNode); |
| } |
| result = true; |
| done: |
| monotonicityInfo[base->getOpnd()] = result; |
| return result; |
| } |
| |
| void DynamicABCE::genBoundConstraint(InvariantOpndLoopInfo* scale, |
| InvariantOpndLoopInfo* baseValue, |
| InvariantOpndLoopInfo* stride, |
| SsaOpnd* arrayLength, |
| bool canReachBound) { |
| Modifier aluMod; |
| ComparisonModifier comMod; |
| Type* int32Type = NULL; |
| SsaOpnd* mulRes = NULL; |
| SsaOpnd* addRes = NULL; |
| Node* newNode = NULL; |
| Node* subGraphExit = NULL; |
| |
| aluMod = Modifier(Overflow_None) | Modifier(Exception_Never) | Modifier(Strict_No); |
| int32Type = typeManager.getInt32Type(); |
| subGraphExit = subGraph->getExitNode(); |
| |
| newNode = subGraph->createBlockNode(instFactory.makeLabel()); |
| |
| if (scale == NULL || (scale->isConstant() && scale->asConstant()->getValue() == 1)) { |
| mulRes = baseValue->getOpnd(); |
| } else { |
| mulRes = opndManager.createSsaTmpOpnd(int32Type); |
| newNode->appendInst(instFactory.makeMul(aluMod, mulRes, |
| scale->getOpnd(), baseValue->getOpnd())); |
| } |
| |
| if (stride == NULL || (stride->isConstant() && stride->asConstant()->getValue() == 0)) { |
| addRes = mulRes; |
| } else { |
| addRes = opndManager.createSsaTmpOpnd(int32Type); |
| newNode->appendInst(instFactory.makeAdd(aluMod, addRes, |
| mulRes, stride->getOpnd())); |
| } |
| |
| comMod = canReachBound ? Cmp_GTE_Un : Cmp_GT_Un; |
| newNode->appendInst(instFactory.makeBranch(comMod, int32Type->tag, |
| addRes, arrayLength, ((Inst*)subGraph->getSpecialExitNode()->getLabelInst())->asLabelInst())); |
| |
| // Insert new node. |
| Edge* inEdge = findUnconditionalInEdge(subGraph->getExitNode()); |
| subGraph->replaceEdgeTarget(inEdge, newNode, false); |
| |
| subGraph->addEdge(newNode, subGraphExit, IN_BOUNDS_PROB); |
| subGraph->addEdge(newNode, subGraph->getSpecialExitNode(), 1 - IN_BOUNDS_PROB); |
| } |
| |
| Node* DynamicABCE::getClonedLoop() { |
| |
| if (clonedLoop != NULL) return clonedLoop; |
| |
| if (Log::isEnabled()) { |
| Log::out() << "Duplicating original loop...\n"; |
| } |
| |
| U_32 maxNodeId = flowGraph.getMaxNodeId(); |
| StlBitVector nodesInLoop(memoryManager, maxNodeId); |
| const Nodes& loopNodes = optimizedLoop->getNodesInLoop(); |
| |
| for (Nodes::const_iterator it = loopNodes.begin(), end = loopNodes.end(); it != end; it++) { |
| Node* node = *it; |
| nodesInLoop.setBit(node->getId()); |
| } |
| |
| DefUseBuilder defUseBuilder(memoryManager); |
| NodeRenameTable nodeRenameTable(memoryManager, loopNodes.size()); |
| OpndRenameTable opndRenameTable(memoryManager, loopNodes.size(), true); |
| |
| defUseBuilder.initialize(flowGraph); |
| |
| clonedLoop = FlowGraph::duplicateRegion(irManager, |
| optimizedLoop->getHeader(), nodesInLoop, defUseBuilder, nodeRenameTable, opndRenameTable); |
| |
| return clonedLoop; |
| } |
| |
| void DynamicABCE::linkSubGraph() { |
| Node* tagetNode = NULL; |
| Edge* inEdge = NULL; |
| |
| if (Log::isEnabled()) { |
| Log::out() << "Inserting condition subgraph:\n"; |
| FlowGraph::printHIR(Log::out(), *subGraph, irManager.getMethodDesc()); |
| } |
| |
| inEdge = findUnconditionalInEdge(optimizedLoop->getHeader()); |
| tagetNode = inEdge->getTargetNode(); |
| |
| // Insert subgraph. |
| flowGraph.spliceFlowGraphInline(inEdge, *subGraph); |
| |
| // Replace subgraph exit. |
| assert(subGraph->getExitNode()->hasOnlyOnePredEdge()); |
| inEdge = subGraph->getExitNode()->getInEdges().front(); |
| flowGraph.replaceEdgeTarget(inEdge, tagetNode, true); |
| |
| // Cleanup phase. |
| dce->eliminateDeadCode(true); |
| dce->eliminateUnreachableCode(); |
| OptPass::computeDominatorsAndLoops(irManager, true); |
| |
| // Retarget all edges from specialExitNode to clonedLoop. |
| while (subGraph->getSpecialExitNode()->getInDegree() != 0) { |
| inEdge = subGraph->getSpecialExitNode()->getInEdges().front(); |
| flowGraph.replaceEdgeTarget(inEdge, getClonedLoop(), true); |
| } |
| |
| /* |
| if (!irManager.isSsaUpdated()) { |
| // TODO: This would not be required if FlowGraph::duplicateRegion or |
| // OptPass::fixupSsa worked better. |
| OptPass::dessa(irManager); |
| OptPass::ssa(irManager); |
| } |
| */ |
| irManager.setSsaUpdated(); |
| // Cleanup phase. |
| dce->eliminateDeadCode(true); |
| dce->eliminateUnreachableCode(); |
| OptPass::computeDominatorsAndLoops(irManager, true); |
| } |
| |
| Edge* DynamicABCE::findUnconditionalInEdge(Node* targetNode) { |
| Edge* inEdge = NULL; |
| const Edges& inEdges = targetNode->getInEdges(); |
| for (Edges::const_iterator it = inEdges.begin(), end = inEdges.end(); it != end; it++) { |
| if (!optimizedLoop->isBackEdge(*it)) { |
| inEdge = *it; |
| break; |
| } |
| } |
| assert(inEdge != NULL); |
| return inEdge; |
| } |
| |
| void DynamicABCE::findArrayAccesses() { |
| ArrayAccessTemplate* arrayAccess = NULL; |
| // Find all array accesses. |
| arrayAccesses.clear(); |
| const Nodes& loopNodes = optimizedLoop->getNodesInLoop(); |
| for (Nodes::const_iterator it = loopNodes.begin(), end = loopNodes.end(); it != end; ++it) { |
| Node* node = *it; |
| for (Inst* inst = (Inst*)node->getFirstInst(); inst != NULL; inst = inst->getNextInst()) { |
| switch (inst->getOpcode()) { |
| case Op_TauCheckBounds: |
| case Op_TauCheckLowerBound: |
| case Op_TauCheckUpperBound: { |
| arrayAccess = new (memoryManager) ArrayAccessTemplate(); |
| fillTemplate(arrayAccess, inst); |
| |
| // Filter out not fully recognized patterns. |
| if (arrayAccess->array != NULL && arrayAccess->index != NULL) { |
| arrayAccesses.push_back(arrayAccess); |
| } else { |
| if (Log::isEnabled()) { |
| Log::out() << "Skip not fully recognized pattern: "; |
| arrayAccess->checkBoundsInst->print(Log::out()); |
| Log::out() << std::endl; |
| } |
| } |
| break; |
| } |
| default:; |
| }; |
| } |
| } |
| } |
| |
| void DynamicABCE::fillTemplate(ArrayAccessTemplate* arrayAccess, Inst* checkInst) { |
| Inst* ldBaseInst = NULL; |
| |
| assert(checkInst->getOpcode() == Op_TauCheckBounds); |
| |
| arrayAccess->checkBoundsInst = checkInst; |
| arrayAccess->index = checkInst->getSrc(1)->asSsaOpnd(); |
| |
| SsaOpnd* lenOpnd = checkInst->getSrc(0)->asSsaOpnd(); |
| Inst* lenInst = lenOpnd->getInst(); |
| |
| if (lenInst->getOpcode() == Op_TauArrayLen) { |
| arrayAccess->array = lenInst->getSrc(0)->asSsaOpnd(); |
| } |
| arrayAccess->arrayLen = lenInst->getDst()->asSsaOpnd(); |
| |
| Node* node = checkInst->getNode()->getUnconditionalEdgeTarget(); |
| for (Inst* inst = (Inst*)node->getFirstInst(); inst != NULL; inst = inst->getNextInst()) { |
| Opcode opcode = inst->getOpcode(); |
| if (opcode == Op_LdArrayBaseAddr) { |
| if (arrayAccess->array == inst->getSrc(0)) { |
| ldBaseInst = inst; |
| } |
| } else if (opcode == Op_AddScaledIndex && |
| arrayAccess->index == inst->getSrc(1) && arrayAccess->array == NULL) { |
| assert(ldBaseInst == NULL); |
| ldBaseInst = inst->getSrc(0)->asSsaOpnd()->getInst(); |
| assert((ldBaseInst->getOpcode() == Op_LdArrayBaseAddr)||(ldBaseInst->getOpcode() == Op_LdVar)); |
| arrayAccess->array = ldBaseInst->getSrc(0)->asSsaOpnd(); |
| break; |
| } |
| } |
| } |
| |
| bool DynamicABCE::isDefInLoop(SsaOpnd* opnd) { |
| return opnd != NULL && optimizedLoop->inLoop(opnd->getInst()->getNode()); |
| } |
| |
| |
| void DynamicABCE::clearAll() { |
| arrayAccesses.clear(); |
| eliminationInfo.clear(); |
| inductionInfo.clear(); |
| optimizedLoop = NULL; |
| clonedLoop = NULL; |
| subGraph = NULL; |
| } |
| |
| } // namespace Jitrino |
