This is an archive of the discontinued LLVM Phabricator instance.

[DSE] Enable MSSA DSE to optimize across PHIs
Needs ReviewPublic

Authored by ebrevnov on Oct 24 2020, 5:12 AM.

Details

Reviewers
fhahn
vdsered
Summary

Currently DSE is unable to optimize stores if there is a phi in between. This patch adds basic support by "phi translating" killing location through phis.

Diff Detail

Event Timeline

ebrevnov created this revision.Oct 24 2020, 5:12 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 24 2020, 5:12 AM
ebrevnov requested review of this revision.Oct 24 2020, 5:12 AM
ebrevnov added a subscriber: fhahn.Oct 24 2020, 5:14 AM
ebrevnov updated this revision to Diff 300594.Oct 26 2020, 1:21 AM

Rename DefLoc to ResDefLoc to fix name conflict.

Great, thanks for sharing!

This currently seems to lead to a bit less stores removed overall on MultiSource/SPEC2000/SPEC2006 with -O3 -flto, but that might be related to some of the limits needing adjustments.

As a first step, it would probably be good to add a set of tests for the new functionality.

Thanks for giving it a try!

Did you use latest update? If not would be nice to remeasure.
Unfortunately, I don't have access to mentioned Spec and not aware of Multisource benchmarks to look on my side. Is it feasible for you to share IR's for several cases so I could take a look? Would be nice to have them in regression test suite anyway.
On the other side I can try to run similar experiment on our internal tests.

This currently seems to lead to a bit less stores removed overall on MultiSource/SPEC2000/SPEC2006 with -O3 -flto, but that might be related to some of the limits needing adjustments.

I found PartialLimit preventing DSE to optimize one of my simple cases. Here is the fix https://reviews.llvm.org/D90371 which I believe is beneficial regardless.

I also noted in case of earlier access is overwritten by the later one from the beginning and the end we DSE only beginning. Did you meet such behavior? Any plans fixing that?

Thanks
Evgeniy

fhahn added a comment.Mar 9 2021, 1:01 PM

Hi! I'm not sure what the current status of this patch is, but I put up an initial patch that just does PHI translation when stepping across memory phis: D98288

Do you think it would be possible to port/add the logic to translate phis for any access?

ebrevnov updated this revision to Diff 339554.Apr 22 2021, 4:06 AM

Extracted small NFC out and rebase

@ebrevnov
Hi, any progress on the patch? I'd like to work on it if you agreed to that.

ebrevnov updated this revision to Diff 355204.Jun 29 2021, 6:16 AM

Extracted more code into separate patches

@ebrevnov
Hi, any progress on the patch? I'd like to work on it if you agreed to that.

Hi Daniil. The help is more than welcome. I've extracted couple of patches which I hope to be able to land as ground work (see dependencies). Next step is to extract minimal change to introduce basic phi translation support. The challenge here is to take best of D98288 and this one as they are doing essentially the same things.

ebrevnov updated this revision to Diff 362669.Jul 29 2021, 1:29 AM

Extracted more stuff to a separate patches.

ebrevnov retitled this revision from [WIP][DSE] Enable MSSA DSE to optimize across PHIs to [DSE] Enable MSSA DSE to optimize across PHIs.Jul 29 2021, 1:41 AM
ebrevnov added reviewers: fhahn, vdsered.

This patch is now close to what I wanted it to be (though I still need to work on comments) and you are welcome to take a look.

ebrevnov updated this revision to Diff 367166.Aug 18 2021, 3:55 AM

Rebase + Formatting

@ebrevnov I see that in memoryIsNotModifiedBetween function and there is some sort of a local phi-translation (I mean it is used only inside this function) as I understand. Do we need to update this function somehow?

ebrevnov edited the summary of this revision. (Show Details)Sep 20 2021, 8:27 AM

@ebrevnov I see that in memoryIsNotModifiedBetween function and there is some sort of a local phi-translation (I mean it is used only inside this function) as I understand. Do we need to update this function somehow?

Looks like this function does phi translation along the way as well. I hope there is an easy way to merge them. Let me try...

IIUC the dependencies for the patch landed by now. Please let me know when this is ready for review. It would also be good to add a brief explanation of the approach both the the description and in code comments.

Also, I think this might need a bit more additional testing by building larger programs. For example, the following example crashes at the moment:

@global = external global i64, align 8

define i32 @widget(i1 %arg, i8* %arg1, i8* %arg2) {
bb:
  store i64 777, i64* @global, align 8
  br i1 %arg, label %bb3, label %bb4

bb3:                                              ; preds = %bb
  %tmp = getelementptr i8, i8* %arg1, i64 1
  store i8 11, i8* %tmp, align 8
  br label %bb4

bb4:                                              ; preds = %bb3, %bb
  %tmp5 = phi i8* [ %arg1, %bb3 ], [ %arg2, %bb ]
  %tmp6 = getelementptr i8, i8* %tmp5, i64 1
  store i8 99, i8* %tmp6, align 8
  ret i32 10
}

Status of this patch?

The ball is on my side but I can't return to it due to other higher priority tasks. Please let me know if there is a demand from your side so I could re-prioritize this one. Also, as mentioned earlier, the help is more than welcome :-)

Herald added a project: Restricted Project. · View Herald TranscriptJul 18 2022, 3:43 AM