This is an archive of the discontinued LLVM Phabricator instance.

[WIP][DSE] Add basic cross-block dse pass using MemorySSA
Needs ReviewPublic

Authored by Tyker on Jan 3 2020, 2:12 PM.



This patch add a cross-block dead store elimination pass that eliminate stores.
This pass work by detecting if a store is observable. this detection has 2 phases. the first phase is a search through the MemorySSA graph for loads or end of function. if on all path in the memssa graph hit a store before they hit a load. if the first phase didn't find any use we passe to the second phase which check if an optimization barrier (throw, fence ...) is reachable between the "dead" store and a killing store. and that all killing store together post-dominate the "dead" store. this pass also has a special case for non-escaping pointers on which we can consider end of function as a killer.

todo in the patch:

  • improve the test suite.

todo probably in separate patchs:

  • measure and tune for compile time impact.
  • fix the many todos in code.
  • handle builtin / library functions.
  • deal with store merging.

todo maybe:

  • improve the pass to deal with partial overwrites.

for a meta build of check-llvm + check-clang here is the stats:

  • sum of dse.* transformation old: 145k this: 202k
  • sum of dse.NumFastStores old: 98k this: 174k

this patch was inspired by D40480
i wasn't planning to post it for review before i improved test but i saw D72146 and we probably should probably try to collaborate.

Diff Detail