From Quasi Paragon
Jump to: navigation, search

There are two flavours of Dead Code Elimination (DCE):

  • Dead assignments
  • Unreachable code

Dead Assignments

Assignments to SSA variables that have no uses can be dropped. If the operation has side-effects, then we want to keep that piece, but we can still drop the SSA variable. This handles the case above where Value Propagation replaced all uses of a variable with its initializer. (Note, Dead Stores to memory are not handled this way.)

Unreachable Code

If a conditional branch has a constant condition, we know which way it'll go at runtime. Therefore we can eliminate the paths from this block to the blocks it doesn't go to. Removing that edge, means we can then remove that alternative from any phi nodes at the start of the target block.

  • If the target block ends up with only one incoming edge from a block with only one outgoing edge, we can then merge those blocks. This will also allow us to replace phi nodes with simple assignments (suitable for another Value Propagation pass).
  • If we removed the only incoming edge to the target block, that block is now unreachable. We can delete all its outgoing edges, and delete the block itself.

A special case to consider when removing edges is that we could end up with no single block unreachable, but a partitioned graph. One of the partitions will be reachable from the start of the function and the other will not. All the blocks in that second partition can be deleted. We can detect this with a simple visiting pass that marks blocks reachable from the start. We only need to do this pass if we delete edges but don't merge or delete one of the two blocks concerned.