This is an archive of the discontinued LLVM Phabricator instance.

[SROA] Fix for PR25873: Pre-splitting should always preserve the partition structure.
AbandonedPublic

Authored by andreadb on Jan 11 2016, 4:52 AM.

Details

Reviewers
chandlerc
Summary

Hi,

This is an attempt to fix PR25873.
When splitting the store of a load, the pre splitting algorithm should check if the store uses a slice of the current alloca. If so, then the algorithm should update the slice information to preserve the partition structure. With this patch, the slice information related to the original store is used to create new slices for the split stores. The original store is eventually marked as dead and its associated slice is "killed".

If we don't update the alloca slices, then we risk to wrongly rewrite the partition of the alloca. I have posted a detailed description of the problem found in bug 25873. The reproducible from PR25873 has been added as a new test case for the existing test SROA/basictest.ll.

Example:

%tmpData = alloca %struct.STest;
...
[0,8):   %3 = load i64, i64* %1, align 8
[8,16):  store i64 %5, i64* %2, align 8

Both load and store use a slice of the %tmpData alloca (slice information is between brackets). In this example, the load is a candidate for pre splitting, and the store is the only user of the load.
Before this patch, the pre splitting algorithm would have rewritten the load/store pair as follows:

[0, 4):   %3 = load i32, i32* %.sroa_cast, align 8
[4, 8):   %4 = load i32, i32* %.sroa_cast1, align 4
[0, 8):   %3 = load i64, i64* %1, align 8   (dead)

      :  store i32 %3, i32* %.sroa_cast3, align 8
      :  store i32 %4, i32* %.sroa_cast5, align 4
[8,16):   store i64 %5, i64* %2, align 8    (dead)

The problem is that no slice information is built for the two new split stores. When the alloca is re-analyzed by SROA, two new problematic partitions are created: [8, 12) [12, 16). Those new partitions would overlap with the already consolidated partition [8, 16).

With this patch, we check if the store uses a slice of the alloca. If so, then we build new slices for the split stores and we mark the previous slice as dead. This is done to ensure that we choose the right partitioning of the alloca for the rewriting stage.
After this patch, the load and store are rewritten as:

[0, 4):   %3 = load i32, i32* %.sroa_cast, align 8
[4, 8):   %4 = load i32, i32* %.sroa_cast1, align 4
[0, 8):   %3 = load i64, i64* %1, align 8   (dead)

[8, 12):  store i32 %3, i32* %.sroa_cast3, align 8
[12,16):  store i32 %4, i32* %.sroa_cast5, align 4
       :   store i64 %5, i64* %2, align 8    (dead)

Please let me know what you think.

Thanks,
Andrea

Diff Detail

Event Timeline

andreadb updated this revision to Diff 44464.Jan 11 2016, 4:52 AM
andreadb retitled this revision from to [SROA] Fix for PR25837: Pre-splitting should always preserve the partition structure..
andreadb updated this object.
andreadb added a reviewer: chandlerc.
andreadb added a subscriber: llvm-commits.

Looks to be a typo - it's PR25873.

andreadb retitled this revision from [SROA] Fix for PR25837: Pre-splitting should always preserve the partition structure. to [SROA] Fix for PR25873: Pre-splitting should always preserve the partition structure..Jan 12 2016, 2:04 AM
andreadb updated this object.

Looks to be a typo - it's PR25873.

Yes, it was the wrong PR. Sorry for the mistake..
I fixed the title and summary (s/PR25837/PR25873).

Again, sorry for the confusion caused.

-Andrea

andreadb updated this revision to Diff 45858.EditedJan 25 2016, 5:30 AM

Ping^2.

Patch rebased.

chandlerc edited edge metadata.Feb 2 2016, 11:25 AM

Sorry its taken so long to cycle back here.

lib/Transforms/Scalar/SROA.cpp
3619–3626

This test is pretty expensive. I think you want to instead build a map from stores to slices above when we are scanning the alloca slices.

3661

You can re-order things to handle the smaller of these cases as an early 'continue' path I think.

Sorry its taken so long to cycle back here.

No problem at all. Thanks for the review!

I will address your comments and post an updated patch.

-Andrea

andreadb updated this revision to Diff 46768.Feb 3 2016, 4:33 AM
andreadb edited edge metadata.

Patch updated based on Chandler's review comments.

I have added a map from stores to slices. That map is populated when we initially scan through the slices of the alloca in 'presplitLoadsAndStores'.
I have also simplified the code adding an early continue as suggested.

Please let me know if this is ok to commit.

Thanks!
Andrea

andreadb updated this revision to Diff 49728.Mar 3 2016, 5:40 AM

Ping! (patch rebased).

Can somebody please review this patch?

Thanks,
Andrea

I'm so, so sorry about this.

Not only for taking so long to get to it, but finally, I understand why I kept being confused when I looked at this patch.

I *COMPLETELY* messed up when I said that this was the correct fix. =[ The root cause of the bug was actually failing to bail out of pre-splitting earlier. There is a simple explanation, and it all stemmed from a previous patch of mine. I just missed a case.

[ =[ =[ =[ =[

I feel really terrible about how much work you've done because I misunderstood the root cause. So sorry about that.

Anyways, the root cause is also *super easy* to fix. I've gone ahead and landed the fix in r263121 using the excellent test case here.

Again, so sorry. =[ =[ =[

I'm so, so sorry about this.

Not only for taking so long to get to it, but finally, I understand why I kept being confused when I looked at this patch.

I *COMPLETELY* messed up when I said that this was the correct fix. =[ The root cause of the bug was actually failing to bail out of pre-splitting earlier. There is a simple explanation, and it all stemmed from a previous patch of mine. I just missed a case.

[ =[ =[ =[ =[

I feel really terrible about how much work you've done because I misunderstood the root cause. So sorry about that.

Anyways, the root cause is also *super easy* to fix. I've gone ahead and landed the fix in r263121 using the excellent test case here.

Again, so sorry. =[ =[ =[

Hey Chandler,

Don't worry! I knew that you have been very busy lately.
For what is worth, overall I don't feel like it was a waste time; at least now I know a bit more about SROA ;-).
Also, we weren't blocked by this issue as internally we had a conservative fix in place.

Anyway, I am very happy that the bug is fixed now.

Thanks,
Andrea

andreadb abandoned this revision.Mar 10 2016, 8:12 AM

Fixed at revision 263121.