Page MenuHomePhabricator

[InstCombine] Shift amount reassociation: shl-trunc-shl pattern
ClosedPublic

Authored by lebedev.ri on Jul 28 2019, 2:46 PM.

Details

Summary

Currently reassociateShiftAmtsOfTwoSameDirectionShifts() only handles two shifts one after another.
If the shifts are shl, we still can easily perform the fold, with no extra legality checks:
https://rise4fun.com/Alive/OQbM

If we have right-shift however, we won't be able to make it any simpler than it already is.

After this the only thing missing here is constant-folding: (NewShAmt >= bitwidth(X))

  • If it's a logical shift, then constant-fold to 0 (not undef)
  • If it's a ashr, then a splat of original signbit

https://rise4fun.com/Alive/E1K
https://rise4fun.com/Alive/i0V

Diff Detail

Repository
rL LLVM

Event Timeline

lebedev.ri created this revision.Jul 28 2019, 2:46 PM
lebedev.ri edited the summary of this revision. (Show Details)Jul 28 2019, 2:54 PM
lebedev.ri edited the summary of this revision. (Show Details)Jul 28 2019, 11:03 PM
xbolva00 added inline comments.Jul 29 2019, 3:45 AM
llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
32 ↗(On Diff #212120)

Is “???” something common in this codebase? I haven’t seen it yet.

Personally I think the code gives better idea what is going on than currently the comment - (Sh0Op0 (???)) is confusing for me.

What do you think?

78 ↗(On Diff #212120)

FIXME:

lebedev.ri marked 3 inline comments as done.

Rebased, addressed review notes.
Ping.

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
78 ↗(On Diff #212120)

Right.

spatel added inline comments.Aug 6 2019, 5:35 AM
llvm/lib/IR/Constants.cpp
1590–1594 ↗(On Diff #213427)

Would we better off copying the codegen sibling API (same type implicitly returns self)?

SelectionDAG::getZExtOrTrunc()

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
39 ↗(On Diff #213427)

That comment isn't clear to me.

"If there is truncation of the shifted value, we must 
adjust the constraints of this fold and recreate that op." ?
lebedev.ri added inline comments.Aug 6 2019, 5:51 AM
llvm/lib/IR/Constants.cpp
1590–1594 ↗(On Diff #213427)

I'm not sure what you have in mind here, ConstantExpr::getZExt()
will (rightfully) assert if zext is unsuitable there.
ConstantExpr::getBitCast() won't, so i suppose i could just use it,
but i really don't need bitcast here, i really want either zext or nothing.

Please can you be more specific as to what you envision here?

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
39 ↗(On Diff #213427)

How about:

If there is a truncation inbetween these two shifts,
we must make note of it, and look through it.
The truncation will impose additional legality checks
on the transform.

?

spatel accepted this revision.Aug 6 2019, 6:31 AM

LGTM

llvm/lib/IR/Constants.cpp
1590–1594 ↗(On Diff #213427)

I'm imagining that we'll eventually (or might already) want the flexibility of returning a constant of arbitrary type (wider or narrower) since that's used in codegen regularly. But that can be a follow-on if we want.

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
39 ↗(On Diff #213427)

That works...just some minor adjustments:

If there is a truncation between the two shifts,
we must make note of it and look through it.
The truncation imposes additional constraints
on the transform.
This revision is now accepted and ready to land.Aug 6 2019, 6:31 AM
lebedev.ri marked 4 inline comments as done.Aug 6 2019, 8:22 AM

Thank you for the review!

llvm/lib/IR/Constants.cpp
1590–1594 ↗(On Diff #213427)

Actually, looking how much extra wrappers there are around e.g. getZExtOrBitCast(),
i think i'm just gonna use it here, not sure i want to add all those and i wouldn't want to leave them out.

This revision was automatically updated to reflect the committed changes.
rnk added a subscriber: rnk.Aug 6 2019, 1:29 PM

This broke the Windows bot:
http://lab.llvm.org:8011/builders/clang-x64-windows-msvc/builds/9418
The failure mode doesn't manifest until the next build due to unrelated issues:
http://lab.llvm.org:8011/builders/clang-x64-windows-msvc/builds/9419

SystemZInstrInfo.cpp fails to compile with an assert. I am working on a reduction and will send it along soon.

rnk added a comment.Aug 6 2019, 1:34 PM

The assertion and stack trace:
https://reviews.llvm.org/P8158
clang: /usr/local/google/home/rnk/llvm-project/llvm/lib/IR/Constants.cpp:1864: static llvm::Constant *llvm::ConstantExpr::get(unsigned int, llvm::Constant *, llvm::Constant *
, unsigned int, llvm::Type *): Assertion `C1->getType() == C2->getType() && "Operand types in binary constant expression should match"' failed.
#9 0x0000000003ca39ae llvm::ConstantExpr::get(unsigned int, llvm::Constant*, llvm::Constant*, unsigned int, llvm::Type*) /usr/local/google/home/rnk/llvm-project/llvm/lib/IR/
Constants.cpp:1896:5
#10 0x00000000036e4fec llvm::ConstantFoldBinaryOpOperands(unsigned int, llvm::Constant*, llvm::Constant*, llvm::DataLayout const&) /usr/local/google/home/rnk/llvm-project/llv
m/lib/Analysis/ConstantFolding.cpp:1286:10

hctim added a subscriber: hctim.Aug 6 2019, 2:59 PM
lebedev.ri marked an inline comment as done.Aug 7 2019, 2:39 AM
In D65380#1617668, @rnk wrote:

The assertion and stack trace:
https://reviews.llvm.org/P8158
clang: /usr/local/google/home/rnk/llvm-project/llvm/lib/IR/Constants.cpp:1864: static llvm::Constant *llvm::ConstantExpr::get(unsigned int, llvm::Constant *, llvm::Constant *
, unsigned int, llvm::Type *): Assertion `C1->getType() == C2->getType() && "Operand types in binary constant expression should match"' failed.

#9 0x0000000003ca39ae llvm::ConstantExpr::get(unsigned int, llvm::Constant*, llvm::Constant*, unsigned int, llvm::Type*) /usr/local/google/home/rnk/llvm-project/llvm/lib/IR/

Constants.cpp:1896:5
#10 0x00000000036e4fec llvm::ConstantFoldBinaryOpOperands(unsigned int, llvm::Constant*, llvm::Constant*, llvm::DataLayout const&) /usr/local/google/home/rnk/llvm-project/llv
m/lib/Analysis/ConstantFolding.cpp:1286:10

Sorry for that and thanks for the revert.