<html>
<head>
<base href="https://bugs.llvm.org/">
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW - Inifinte loop in ScalarEvolotion involving isImpliedCond"
href="https://bugs.llvm.org/show_bug.cgi?id=51869">51869</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Inifinte loop in ScalarEvolotion involving isImpliedCond
</td>
</tr>
<tr>
<th>Product</th>
<td>libraries
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>Linux
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>enhancement
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>Global Analyses
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>bjorn.a.pettersson@ericsson.com
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org, max.kazantsev@azul.com
</td>
</tr></table>
<p>
<div>
<pre>Created <span class=""><a href="attachment.cgi?id=25260" name="attach_25260" title="bbi-59764-2.ll">attachment 25260</a> <a href="attachment.cgi?id=25260&action=edit" title="bbi-59764-2.ll">[details]</a></span>
bbi-59764-2.ll
Given the bbi-50881-2.ll test input this command seem to hang
opt -indvars bbi-59764-2.ll
Bi-secting points at:
commit 5ef84688fba28b9f0f69ddc9a5beb75b10696798
Author: Max Kazantsev <<a href="mailto:mkazantsev@azul.com">mkazantsev@azul.com</a>>
Date: Wed Oct 28 13:28:39 2020 +0700
Re-enable "[SCEV] Prove implications of different type via truncation"
When we need to prove implication of expressions of different type width,
the default strategy is to widen everything to wider type and prove in this
type. This does not interact well with AddRecs with negative steps and
unsigned predicates: such AddRec will likely not have a `nuw` flag, and its
`zext` to wider type will not be an AddRec. In contraty, `trunc` of an
AddRec
in some cases can easily be proved to be an `AddRec` too.
This patch introduces an alternative way to handling implications of
different
type widths. If we can prove that wider type values actually fit in the
narrow type,
we truncate them and prove the implication in narrow type.
The return was due to revert of underlying patch that this one depends on.
Unit test temporarily disabled because the required logic in SCEV is
switched
off due to compile time reasons.
Differential Revision: <a href="https://reviews.llvm.org/D89548">https://reviews.llvm.org/D89548</a>
The code looks like this:
bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
const SCEV *RHS,
ICmpInst::Predicate FoundPred,
const SCEV *FoundLHS, const SCEV *FoundRHS,
const Instruction *Context) {
// Balance the types.
if (getTypeSizeInBits(LHS->getType()) <
getTypeSizeInBits(FoundLHS->getType())) {
// For unsigned and equality predicates, try to prove that both found
// operands fit into narrow unsigned range. If so, try to prove facts in
// narrow types.
if (!CmpInst::isSigned(FoundPred) && !FoundLHS->getType()->isPointerTy()) {
auto *NarrowType = LHS->getType();
auto *WideType = FoundLHS->getType();
auto BitWidth = getTypeSizeInBits(NarrowType);
const SCEV *MaxValue = getZeroExtendExpr(
getConstant(APInt::getMaxValue(BitWidth)), WideType);
if (isKnownPredicate(ICmpInst::ICMP_ULE, FoundLHS, MaxValue) &&
isKnownPredicate(ICmpInst::ICMP_ULE, FoundRHS, MaxValue)) {
const SCEV *TruncFoundLHS = getTruncateExpr(FoundLHS, NarrowType);
const SCEV *TruncFoundRHS = getTruncateExpr(FoundRHS, NarrowType);
if (isImpliedCondBalancedTypes(Pred, LHS, RHS, FoundPred,
TruncFoundLHS,
TruncFoundRHS, Context))
return true;
}
}
...
I don't remember exactly but I think my quick hack with adding some debug
printouts indicated that the
isKnownPredicate(ICmpInst::ICMP_ULE, FoundRHS, MaxValue)
call might end up in some recursion, but I'm not 100% sure that is the problem.</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>