This is an archive of the discontinued LLVM Phabricator instance.

[DSE] Sink a memory access if it is only alive in one successor.
Needs ReviewPublic

Authored by StephenFan on Oct 18 2022, 7:02 PM.

Details

Summary

If a memory access is only alive in one successor, sinking the instruction
of this memory access to the alive successor will make the program execute one
less instruction if it goes to dead successors(successors except the
alive successor).

Since deleting instruction is more beneficial than sinking, sinking will
be doing until we have deleted all dead instructions.

It seems to have no effect on on compile time: https://llvm-compile-time-tracker.com/compare.php?from=6eb40bf51b768672218539935f60ce55ae6ad750&to=e8bccfd7a3c58f3287f7da7ab3e2582ec270b0f4&stat=instructions

Diff Detail

Event Timeline

StephenFan created this revision.Oct 18 2022, 7:02 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 18 2022, 7:02 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
StephenFan requested review of this revision.Oct 18 2022, 7:02 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 18 2022, 7:02 PM

Fix CI error.

alex added a subscriber: alex.Oct 24 2022, 2:38 PM

This is great! A couple of things I noticed on my test case:

  1. This doesn't handle the case in which you might sink a store into a basic block that reads it (in my test case, it's a throwing instruction), because the check for readers will kick in and return None from getDomMemoryDef() before ever getting to check whether it can sink the store. I guess to fix this we could track reading instructions, instead of bailing out immediately, and see if they are all inside or dominated by SuccToSinkTo. If so, we should be able to safely sink the store, I think?
  1. This doesn't handle the slow CFG search that kicks in if there are unreachable instructions. We could presumably detect sink targets there too.

Both of these things could be followups of course. :)

This is great! A couple of things I noticed on my test case:

  1. This doesn't handle the case in which you might sink a store into a basic block that reads it (in my test case, it's a throwing instruction), because the check for readers will kick in and return None from getDomMemoryDef() before ever getting to check whether it can sink the store. I guess to fix this we could track reading instructions, instead of bailing out immediately, and see if they are all inside or dominated by SuccToSinkTo. If so, we should be able to safely sink the store, I think?
  1. This doesn't handle the slow CFG search that kicks in if there are unreachable instructions. We could presumably detect sink targets there too.

Both of these things could be followups of course. :)

Thanks a lot for testing it and making suggestions. I will try to solve these cases these days.

This is great! A couple of things I noticed on my test case:

  1. This doesn't handle the case in which you might sink a store into a basic block that reads it (in my test case, it's a throwing instruction), because the check for readers will kick in and return None from getDomMemoryDef() before ever getting to check whether it can sink the store. I guess to fix this we could track reading instructions, instead of bailing out immediately, and see if they are all inside or dominated by SuccToSinkTo. If so, we should be able to safely sink the store, I think?
  1. This doesn't handle the slow CFG search that kicks in if there are unreachable instructions. We could presumably detect sink targets there too.

Both of these things could be followups of course. :)

I don't get the point of your second suggestion, do you mind giving a test case? :)

  1. Don't bail out immediatly if has read clobber.
  2. Handle the slow CFG search.