in vm/jitrino/src/optimizer/dabce.cpp [402:585]
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;
}