Notes from writing the basic MemorySSA-backed global DSE https://reviews.llvm.org/D29624

dse-catalog.md

• stores with no dependency (post-order traversal reaches end of mssa):

  • store to alloca
    • dead on unwind, so elim even if

• store post-dommed regular store

  • should must-alias or partial-alias the first store

• store post-dommed by a free, lifetime_end

  • should must-alias or partial-alias the store

• store immediately dominated by a free, lifetime_end

  • kill if must-alias

• the memcpy(B, A); memcpy(B, B) case of isPossibleSelfRead is invalid. memcpy ops are forbidden by LangRef from aliasing. if it were a memmove, then:

  store 0, B
  memmove(B, B)
  store 1, B
  

  is equivalent to,

  store 0, B
  x = load B
  store x, B    ; this can't hoist above the load
  store 1, B
  

  the second store to B can DSE the first only if the memmove is DSE-ed, e.g.,

  store 0, B
  memmove(B, B)
  store 1, B
  
  =>
  
  store 0, B
  store 1, B
  
  =>
  
  store 1, B
  

• fork in the mssa tree is equivalent to the split point having more than one memory-defining use.

formal definitions

core conditions of dse:

store 0, A
...
store 1, A  ; must-aliases and post-doms above store.

additional conditions:

• "..." can't contain anything that must-/may-ref A.
• "..." can't contain anything that throws if and only if A escapes the function. an example of non-escaping A would be an alloca.

as long as theses conditions are satisfied, the earlier store may be deleted. special cases:

• no-op stores count as dead:
  • if the store immediately follows a must-alias load.
  • memmove with must-aliased operands.
• any unused store to A counts as dead if:
  • A doesn't escapem, or
  • the store is post-dominated by free/lifetime_end.
• any store dominated by a call to free or lifetime_end is dead.

questions

• ssupre is under patent since 1998.

• mssa fails to detect the redundancy:

  y = load x
  while (undef) { store y, x; ... }
  

  because the clobber walker starts at the store and hits its parent phi.

• the clobber walker also fails for:

  ; 1 = MemoryDef(liveOnEntry)
  y = load volatile/atomic x
  ; 2 = MemoryDef(1)
  store y, x;
  

• how to detect intervening throws more precisely than rpo indexing?

` vim: set syntax=markdown textwidth=0 tabstop=2 shiftwidth=2:

questions

does clobber walker find defs? p not
can handle nonlocal natively? yes.
allocainst has memoryaccess? no