Page MenuHomePhabricator

[DAGCombiner] Fix infinite loop in vector mul/shl combining
ClosedPublic

Authored by john.brawn on Nov 14 2016, 6:08 AM.

Details

Summary

We have the following DAGCombiner transformations:

(mul (shl X, c1), c2) -> (mul X, c2 << c1)
(mul (shl X, C), Y) -> (shl (mul X, Y), C)
(shl (mul x, c1), c2) -> (mul x, c1 << c2)

Usually the constant shift is optimised by SelectionDAG::getNode when it is constructed, by SelectionDAG::FoldConstantArithmetic, but when we're dealing with vectors and one of those vector constants contains an undef element FoldConstantArithmetic does not fold and we enter an infinite loop.

Fix this by making FoldConstantArithmetic use getNode to decide how to fold each vector element, the same as FoldConstantVectorArithmetic does, and rather than adding the constant shift to the work list instead only apply the transformation if it's already been folded into a constant, as if it's not we're going to loop endlessly. Additionally add missing NoOpaques to one of those transformations, which I noticed when writing the tests for this.

Diff Detail

Repository
rL LLVM

Event Timeline

john.brawn updated this revision to Diff 77796.Nov 14 2016, 6:08 AM
john.brawn retitled this revision from to [DAGCombiner] Fix infinite loop in vector mul/shl combining.
john.brawn updated this object.
john.brawn added reviewers: RKSimon, bogner, spatel.
john.brawn set the repository for this revision to rL LLVM.
john.brawn added a subscriber: llvm-commits.
RKSimon added inline comments.Nov 14 2016, 6:36 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2163 ↗(On Diff #77796)

asserts need a message : assert(isConstantOrConstantVector(C3) && "Failed to constant fold");

4717 ↗(On Diff #77796)

asserts need a message : assert(isConstantOrConstantVector(Shl) && "Failed to constant fold");

lib/CodeGen/SelectionDAG/SelectionDAG.cpp
3476 ↗(On Diff #77796)

I don't think this is safe (e.g. OR(C1, UNDEF) --> at least C1).

john.brawn added inline comments.Nov 14 2016, 7:06 AM
lib/CodeGen/SelectionDAG/SelectionDAG.cpp
3476 ↗(On Diff #77796)

Hmm, I'd thought that FoldConstantVectorArithmetic folds any undef input element into an undef output element, but looking more closely it calls getNode on each element pair and it's only for some operations that results in undef. I'll try making FoldConstantArithmetic do the same.

john.brawn updated this revision to Diff 77826.Nov 14 2016, 9:23 AM
john.brawn updated this object.

Update according to review comments.

RKSimon edited edge metadata.Nov 14 2016, 10:23 AM

Please can we have a diff with context?

john.brawn updated this revision to Diff 77963.Nov 15 2016, 2:38 AM
john.brawn edited edge metadata.

Added context to diff.

RKSimon added inline comments.Nov 15 2016, 5:40 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2163 ↗(On Diff #77963)

I'm worried that maybe instead of asserting for a constant value we should just use an if() - there still might end up being odd cases where the constant fold still fails for some reason. Same for the other case below. What do you think?

lib/CodeGen/SelectionDAG/SelectionDAG.cpp
3476 ↗(On Diff #77963)

These aren't APInt any more:

// FIXME: This is valid and could be handled by truncation.
john.brawn added inline comments.Nov 16 2016, 10:22 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
2163 ↗(On Diff #77963)

Sounds reasonable, I'll update the patch (though not until next week as I'll be on holiday).

john.brawn updated this revision to Diff 79077.Nov 23 2016, 7:31 AM
john.brawn updated this object.

Patch updated according to review comments.

RKSimon accepted this revision.Nov 23 2016, 7:54 AM
RKSimon edited edge metadata.

LGTM

This revision is now accepted and ready to land.Nov 23 2016, 7:54 AM
This revision was automatically updated to reflect the committed changes.