Page MenuHomePhabricator

[InstCombine] Try to resubmit the combine of A->B->A BitCast and fix for pr27996
ClosedPublic

Authored by Carrot on Aug 25 2016, 4:56 PM.

Details

Summary

The original patch of the A->B->A BitCast optimization was reverted by r274094 because it may cause infinite loop inside compiler https://llvm.org/bugs/show_bug.cgi?id=27996.

The problem is with following code

xB = load (type B);
xA = load (type A);
+yA = (A)xB; B -> A
+zAn = PHI[yA, xA];
PHI
+zBn = (B)zAn; // A -> B
store zAn;
store zBn;

optimizeBitCastFromPhi generates

+zBn = (B)zAn; // A -> B

and expects it will be combined with the following store instruction to another

store zAn

Unfortunately before combineStoreToValueType is called on the store instruction, optimizeBitCastFromPhi is called on the new BitCast again, and this pattern repeats indefinitely.

optimizeBitCastFromPhi only generates BitCast for load/store instructions, and BitCast with load/store instructions can easily be handled by InstCombineLoadStoreAlloca.cpp. So the solution to the problem is if all users of a CI are load/store instructions, we should not do optimizeBitCastFromPhi on it. Then optimizeBitCastFromPhi will not be called on the new BitCast instructions.

Diff Detail

Repository
rL LLVM

Event Timeline

Carrot updated this revision to Diff 69303.Aug 25 2016, 4:56 PM
Carrot retitled this revision from to [InstCombine] Try to resubmit the combine of A->B->A BitCast and fix for pr27996 .
Carrot updated this object.
Carrot added reviewers: majnemer, evstupac.
Carrot added a subscriber: llvm-commits.
evstupac edited edge metadata.Sep 8 2016, 10:52 PM

Hi,

InstCombine is supposed to run to fix-point

Have you addressed David's comment?

Am I right that current fix-point is when all CI users are memory instructions?

Thanks,
Evgeny

lib/Transforms/InstCombine/InstCombineCasts.cpp
1806 ↗(On Diff #69303)

To follow one stile you I'd put LI definition into comparison.

Carrot added a comment.Sep 9 2016, 1:44 PM

Hi,

InstCombine is supposed to run to fix-point

Have you addressed David's comment?

Am I right that current fix-point is when all CI users are memory instructions?

Yes, optimizeBitCastFromPhi only generates new BitCast for load/store instructions, and now it will not work on BitCast used by MemOp only, so it will never work on the BitCast generated by itself.

Yes, optimizeBitCastFromPhi only generates new BitCast for load/store instructions,

In the code I see Constants as well.
It would be nice to have more comments at return explaining why this is a fix point.

lib/Transforms/InstCombine/InstCombineCasts.cpp
1860 ↗(On Diff #69303)

New BitCast instruction is created if one of OldPN operands is Load, right?

L = Load
X = Phi [L, ...]

To:

L = Load
NewL = BitCast (L)
NewX = Phi [NewL, ...]

The new BitCast instruction user is PHI, not Load or Store.
Will it pass your fix point?

Yes, optimizeBitCastFromPhi only generates new BitCast for load/store instructions,

In the code I see Constants as well.

I expect the BitCasted Constant will be returned by instruction builder directly.

lib/Transforms/InstCombine/InstCombineCasts.cpp
1860 ↗(On Diff #69303)

This function is called on the following pattern

p = Phi [...]
b =BitCast(p)

The BitCast of Load is not a candidate of this optimization.

evstupac added inline comments.Sep 14 2016, 5:02 PM
lib/Transforms/InstCombine/InstCombineCasts.cpp
1768 ↗(On Diff #69303)

Here you check that for
b = BitCast(p)
All Users are
"st b", "st to address b" or "ld from address b"
I don't see how your transformation can create BitCast for "load form b".

Carrot updated this revision to Diff 71713.Sep 16 2016, 4:17 PM
Carrot edited edge metadata.
Carrot marked 2 inline comments as done.

Change the hasMemOpUsersOnly to hasStoreUsersOnly.

Carrot added inline comments.Sep 19 2016, 11:20 AM
lib/Transforms/InstCombine/InstCombineCasts.cpp
1768 ↗(On Diff #69303)

You are right. And BitCast used by Load is not handled by InstCombineLoadStoreAlloca.cpp.

evstupac added inline comments.Sep 23 2016, 4:52 PM
lib/Transforms/InstCombine/InstCombineCasts.cpp
1768 ↗(On Diff #71713)

Ok.
You are generating BitCast only for 1 store operand:
SI->setOperand(0, Builder->CreateBitCast(NewPNodes[PN], SrcTy));

Here you are exiting if BitCast goes to one of store operand (0 or 1). What is the reason?

1879 ↗(On Diff #71713)

Could you please insert an assert on newly Created BitCast (to be sure we'll not hit it on next iteration)?

Carrot updated this revision to Diff 72727.Sep 27 2016, 4:05 PM
Carrot marked an inline comment as done.
Carrot added inline comments.
lib/Transforms/InstCombine/InstCombineCasts.cpp
1768 ↗(On Diff #71713)

Because the following case

bitcast oldval to val
store val, addr

can be handled by InstCombineLoadStoreAlloca.cpp, and transformed to

bitcast addr to addr_with_diff_type
store oldval, addr_with_diff_type

This is the form you have question. It can be further transformed to

store oldval, (bitcast addr to addr_with_diff_type)

This is an optimized result.

majnemer added inline comments.Oct 21 2016, 2:14 PM
lib/Transforms/InstCombine/InstCombineCasts.cpp
1765 ↗(On Diff #72727)

"Store" should probably be "StoreInsts".

1767–1771 ↗(On Diff #72727)

I think this can be simplified to llvm::all_of(CI.users(), [](User *U) { return isa<StoreInst>(U); });

1878 ↗(On Diff #72727)

This looks unidiomatic. I'd cast<BitCastInst> the result of CreateBitCast. CreateBitCast cannot be a Constant because its operand is a PHINode.

Carrot updated this revision to Diff 75609.Oct 24 2016, 10:14 AM
Carrot marked 2 inline comments as done.
Carrot added inline comments.
lib/Transforms/InstCombine/InstCombineCasts.cpp
1767–1771 ↗(On Diff #72727)

It is also used by following assert statement, so it's better to just leave it here.

majnemer added inline comments.Oct 24 2016, 10:26 AM
lib/Transforms/InstCombine/InstCombineCasts.cpp
1896 ↗(On Diff #75609)

I'd hoist this cast<BitCastInst> over to the call to Builder->CreateBitCast

Carrot updated this revision to Diff 75653.Oct 24 2016, 3:14 PM
Carrot marked an inline comment as done.
majnemer added inline comments.Oct 24 2016, 3:39 PM
lib/Transforms/InstCombine/InstCombineCasts.cpp
1873 ↗(On Diff #75653)

It'd be more obvious why you don't need to mess with the builder insertion point if you used ConstantExpr::getBitCast instead.

1875–1876 ↗(On Diff #75653)

I think this would do the wrong thing if the incoming block was an EH pad. Could we insert the bitcast after LI?

1893–1894 ↗(On Diff #75653)

auto *, also please clang-format this line.

Carrot updated this revision to Diff 75716.Oct 25 2016, 9:16 AM
Carrot marked 3 inline comments as done.
majnemer accepted this revision.Oct 25 2016, 10:29 AM
majnemer edited edge metadata.

LGTM

This revision is now accepted and ready to land.Oct 25 2016, 10:29 AM
This revision was automatically updated to reflect the committed changes.