PR35710: Nary reassociation falls into infinite loop

[evstupac]

Summary

The following example:
define i8 @foo(i8 %v) local_unnamed_addr #0 {
region.0:

%0 = mul nsw i8 16, %v 
%1 = mul nsw i8 0, %0 
%2 = mul nsw i8 1, %1 
ret i8 %2

}
Causes nary reassociation to fall into infinite loop.
The root cause is in overflowed SCEV expression (16*v)*(16*v) - which is 0 for "i8" type.

The patch inserts a check to avoid the case.

[evstupac]

To be more precise NaryReassociation works that way:
r0 = v * 16
r1= r0 * 0
r2 = r1 * 1

When reassociating r2 = r1 * 1:
r2 = ((v * 16) * 0) * 1

RHS = 1
Aexpr = 0
Bexpr = 16 * v

We look for findClosestMatchingDominator(0 * 1). It is r1.
That way new Instruction becomes:
r2 = r1 * r0 - which is ok.

Next step for this instruction r2 = r1 * r0:
r2 = ((v * 16) * 0) * (v * 16)

RHS = 16 *v
Aexpr = 0
Bexpr = 16 * v

We look for findClosestMatchingDominator((16 * v) * (16 * v)). It is r1 (because 16 * v * 16 * v = 0 for "i8" type.
That way new Instruction becomes:
r2 = r1 * 0

And it becomes infinite loop...

[evstupac]

PING

[evstupac]

PING2

[hfinkel]

lib/Transforms/Scalar/NaryReassociate.cpp

466 ↗

(On Diff #127789)

If I hadn't read the description, I'd have no idea what this meant (and I'm still not entirely sure). How does this detect overflow? Is it fair to say that x*0 is a special case because it can be replicated arbitrarily-many times in products (because it is equal to 0, and thus, so is any product of which it is a part), and that can lead to infinite loops.

[evstupac]

lib/Transforms/Scalar/NaryReassociate.cpp

466 ↗

(On Diff #127789)

The change is about to limit current implementation, which works fine with zeros. However, it does not expect to see 0 as a result of 2 non-zero expressions product (LHSExpr here).

[hfinkel]

lib/Transforms/Scalar/NaryReassociate.cpp

466 ↗

(On Diff #127789)

What doesn't expect to see a zero as the result of two non-zero expressions? And here we're also checking that RHS is foldable to zero? Which two expressions are non-zero?

[evstupac]

lib/Transforms/Scalar/NaryReassociate.cpp

466 ↗

(On Diff #127789)

comment on lines 445, 446 to support my answers below:

// I = (A op B) op RHS
//   = (A op RHS) op B or (B op RHS) op A

What doesn't expect to see a zero as the result of two non-zero expressions?

LHSExpr which is product of BExpr, RHSExpr for the case.

And here we're also checking that RHS is foldable to zero?

Yes. RHS is "A" for the case.

Which two expressions are non-zero?

RHSExpr and BExpr are non-zero.

Please look at my Dec 21 comment. I've tried to explain the case there using source code names.

Thinking more about this I think it will be correct to exit earlier at line 443 if RHS is foldable to zero and instruction is multiplication. I can update patch that way. Whatever you prefer more.

[evstupac]

Leave only zero check and move it to an earlier stage.

[evstupac]

PING

llvm/trunk/lib/Transforms/Scalar/NaryReassociate.cpp

GetElementPtrInst *NewGEP =
       cast<GetElementPtrInst>(Builder.CreateGEP(Candidate, RHS));
   NewGEP->setIsInBounds(GEP->isInBounds());
   NewGEP->takeName(GEP);
   return NewGEP;
 }
 
 Instruction *NaryReassociatePass::tryReassociateBinaryOp(BinaryOperator *I) {
   Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
+  // There is no need to reassociate 0.
+  if (SE->getSCEV(I)->isZero())
+    return nullptr;
   if (auto *NewI = tryReassociateBinaryOp(LHS, RHS, I))
     return NewI;
   if (auto *NewI = tryReassociateBinaryOp(RHS, LHS, I))
     return NewI;
   return nullptr;
 }
 
 Instruction *NaryReassociatePass::tryReassociateBinaryOp(Value *LHS, Value *RHS,

llvm/trunk/test/Transforms/NaryReassociate/pr35710.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -nary-reassociate -S | FileCheck %s
+
+; The test check that compilation does not fall into infinite loop.
+
+define i8 @foo(i8 %v) local_unnamed_addr #0 {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  region.0:
+; CHECK-NEXT:    [[TMP0:%.*]] = mul nsw i8 16, [[V:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = mul nsw i8 0, [[TMP0]]
+; CHECK-NEXT:    [[TMP2:%.*]] = mul nsw i8 1, [[TMP1]]
+; CHECK-NEXT:    ret i8 [[TMP2]]
+;
+region.0:
+  %0 = mul nsw i8 16, %v
+  %1 = mul nsw i8 0, %0
+  %2 = mul nsw i8 1, %1
+  ret i8 %2
+}