This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] PR30366 : Teach the udiv folding logic how to handle constant expressions.
ClosedPublic

Authored by andreadb on Sep 14 2016, 8:26 AM.

Details

Summary

This patch fixes PR30366.

Function 'foldUDivShl' works under the assumption that the value in input to the function is always an llvm::Instruction.
However, function 'visitUDivOperand' (the only user of 'foldUDivShl') clearly violates that precondition since it uses pattern matchers to check if the udiv can be folded. Internally, pattern matchers for binary operators know how to work with both Instruction and ConstantExpr values.

This causes problems with instructions like this one:

udiv i32 %z, zext (i16 shl (i16 1, i16 ptrtoint ([1 x i16]* @b to i16)) to i32)

Where:
Op1 = zext (i16 shl (i16 1, i16 ptrtoint ([1 x i16]* @b to i16)) to i32)

Internally, function 'visitUDivOperand' uses the following matcher:

match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))

In our example, that matcher would return 'true'. However, Op1 is a ConstantExpr and not an Instruction! Later on, Op1 is passed in input to foldUDivShl ; that function attempts to simplify the udiv instruction according to the following rule:

// X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)

The code in foldUDivShl explicitly casts Op1 to llvm::Instruction. In our example, this would trigger an assertion failure due to an invalid cast from ConstantExpr to Instruction.

This patch fixes the problem in foldUDivShl() using pattern matchers instead of using explicit casts. The reduced test case from pr30366 has been added to test file InstCombine/udiv-simplify.ll.

Please let me know if okay to commit.

Thanks,
Andrea

Diff Detail

Event Timeline

andreadb updated this revision to Diff 71364.Sep 14 2016, 8:26 AM
andreadb retitled this revision from to [InstCombine] PR30366 : Teach the udiv folding logic how to handle constant expressions..
andreadb updated this object.
andreadb added reviewers: spatel, RKSimon, uabelho.
andreadb added a subscriber: llvm-commits.
majnemer added inline comments.
lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1002

You should check if match fails.

Hi David,

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1002

In theory, this check should never fail because visitUDivOperand (see lines 1036:1040) always checks that Op1 is a left shift of a power_of_2 before adding 'foldUDivShl' to the set of folding actions.

Would it be okay if I add an assertion failure if the call to match returns false?

majnemer added inline comments.Sep 14 2016, 10:28 AM
lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1002

Yes, something like:

if (!match(...))
  llvm_unreachable("match shouldn't fail here!");
1004–1005

This looks strangely formatted.

Thanks for the feedback David!

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1002

I will add that check.

1004–1005

Sorry, I forgot to clang-format this patch. I will fix it.

andreadb updated this revision to Diff 71392.Sep 14 2016, 10:42 AM

Patch updated.

Addressed David's review comments.

Ping.

Okay to commit?

uabelho edited edge metadata.Sep 22 2016, 12:59 AM

The patch solves PR30366 which I wrote and I haven't seen any problems when I've used it so I'd like to see it merged as well.

spatel accepted this revision.Sep 23 2016, 2:04 PM
spatel edited edge metadata.

LGTM. See inline comments for a couple of nits.

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
993

It would be helpful to add a comment about the optional zext that we are pattern matching.

996

Unnecessary to initialize to nullptr here?

This revision is now accepted and ready to land.Sep 23 2016, 2:04 PM
This revision was automatically updated to reflect the committed changes.

Thanks Andrea!