[DSE] Enable MSSA DSE to optimize across PHIs

[ebrevnov]

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.

[ebrevnov]

Rename DefLoc to ResDefLoc to fix name conflict.

[fhahn]

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.

[ebrevnov]

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.

[ebrevnov]

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]

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]

Extracted small NFC out and rebase

[vdsered]

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

[ebrevnov]

Rebase

[ebrevnov]

Extracted more code into separate patches

[ebrevnov]

In D90095#2843496, @vdsered wrote:

@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]

Extracted more stuff to a separate patches.

[ebrevnov]

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]

Rebase + Formatting

[vdsered]

@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]

Rebase

[ebrevnov]

In D90095#2992286, @vdsered wrote:

@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...

[fhahn]

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
}

[xbolva00]

Status of this patch?

[ebrevnov]

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 :-)