Page MenuHomePhabricator

PR35710: Nary reassociation falls into infinite loop
ClosedPublic

Authored by evstupac on Dec 20 2017, 2:49 PM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

evstupac created this revision.Dec 20 2017, 2:49 PM
fhahn added a subscriber: fhahn.Dec 20 2017, 4:04 PM

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...

davide added a subscriber: davide.
hfinkel added a subscriber: hfinkel.Jan 4 2018, 7:08 PM
hfinkel added inline comments.
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 added inline comments.Jan 4 2018, 10:33 PM
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 added inline comments.Jan 6 2018, 9:24 PM
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 added inline comments.Jan 10 2018, 4:19 PM
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 updated this revision to Diff 133671.Feb 9 2018, 12:58 PM

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

pankajchawla accepted this revision.Mar 2 2018, 5:27 PM
This revision is now accepted and ready to land.Mar 2 2018, 5:27 PM
This revision was automatically updated to reflect the committed changes.