This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] DCE instructions earlier
ClosedPublic

Authored by nikic on Feb 22 2020, 2:06 AM.

Details

Summary

When InstCombine initially populates the worklist, it already performs constant folding and DCE. However, as the instructions are initially visited in program order, this DCE can pick up only the last instruction of a dead chain, the rest would only get picked up in the main InstCombine run.

To avoid this, we instead perform the DCE in separate pass over the collected instructions in reverse order, which will allow us to pick up full dead instruction chains. We already need to do this reverse iteration anyway to populate the worklist, so this shouldn't add extra cost.

This by itself only fixes a small part of the problem though: The same basic issue also applies during the main InstCombine loop. We generally always want DCE to occur as early as possible, because it will allow one-use folds to happen. Address this by also performing DCE while adding deferred instructions to the main worklist.

This drops the number of tests that perform more than 2 InstCombine iterations from ~80 to ~40. There's some spurious test changes due to operand order / icmp toggling.

Diff Detail

Event Timeline

nikic created this revision.Feb 22 2020, 2:06 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 22 2020, 2:06 AM
nikic updated this revision to Diff 246071.Feb 22 2020, 2:54 AM

Update a test case outside the InstCombine directory.

spatel added inline comments.Feb 26 2020, 5:32 AM
llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
3418

Seems like we already have redundant lines between this and what is included within "eraseInstFromFunction()". Can we:

  1. Remove the debug print.
  2. Remove the set of MadeIRChange.

That could be a preliminary NFC cleanup for the existing call below this block too?

3682–3687

eraseInstFromFunction(*Inst) ?

nikic updated this revision to Diff 246805.Feb 26 2020, 11:46 AM
nikic marked an inline comment as done.

Rebase and remove redundant code.

nikic marked 3 inline comments as done.Feb 26 2020, 11:48 AM
nikic added inline comments.
llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
3418

Done that in rG7da3b5e45c25 for the existing use, and here as well.

3682–3687

We can't use eraseInstFromFunction() here, because it will also push operands to the worklist. As this is the code doing the initial worklist population, these would interfere.

spatel accepted this revision.Feb 27 2020, 7:32 AM

LGTM

llvm/lib/Transforms/InstCombine/InstCombineInternal.h
728

I guess it's independent of this patch, but I'm confused about when it's appropriate to push() vs. add(). Will we eventually reach a state where push() is private to the worklist implementation, and all the user code should use add()?

This revision is now accepted and ready to land.Feb 27 2020, 7:32 AM
nikic marked 2 inline comments as done.Feb 27 2020, 8:20 AM
nikic added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineInternal.h
728

Generally yes, user code should use add() and things are slowly moving in that direction...

Normally the choice of add() (FIFO, what you usually want) vs push() (LIFO) is about order. In this case there is no clear order in which the operands should be processed, so either is fine. I'm only using add() because the extra DCE code added in this patch works by processing the deferred worklist.

I think in the future, we may want to have a separate worklist only for DCE (instead of reusing the deferred worklist), and separate out add() vs addForDCE(). I'm leaving that for later, as I'm not sure whether it's sufficient to only perform DCE (rather than a full revisit) if the use-count drops.

This revision was automatically updated to reflect the committed changes.