[llvm-bugs] [Bug 51869] New: Inifinte loop in ScalarEvolotion involving isImpliedCond

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=51869

            Bug ID: 51869
           Summary: Inifinte loop in ScalarEvolotion involving
                    isImpliedCond
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Global Analyses
          Assignee: unassignedbugs at nondot.org
          Reporter: bjorn.a.pettersson at ericsson.com
                CC: llvm-bugs at lists.llvm.org, max.kazantsev at azul.com

Created attachment 25260
  --> https://bugs.llvm.org/attachment.cgi?id=25260&action=edit
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 <mkazantsev at azul.com>
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: https://reviews.llvm.org/D89548


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.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20210915/4c1e8cee/attachment-0001.html>