Page MenuHomePhabricator

[Canonicalizer] Process regions top-down instead of bottom up & reuse existing constants.

Authored by lattner on Mar 19 2021, 9:22 PM.



This reapplies b5d9a3c / with a one line fix in
processExistingConstants to skip() when erasing a constant we've already seen.

Original commit message:

  1. Change the canonicalizer to walk the function in top-down order instead of bottom-up order. This composes well with the "top down" nature of constant folding and simplification, reducing iterations and re-evaluation of ops in simple cases.
  2. Explicitly enter existing constants into the OperationFolder table before canonicalizing. Previously we would "constant fold" them and rematerialize them, wastefully recreating a bunch fo constants, which lead to pointless memory traffic.

Both changes together provide a 33% speedup for canonicalize on some mid-size
CIRCT examples.

One artifact of this change is that the constants generated in normal pattern
application get inserted at the top of the function as the patterns are applied.
Because of this, we get "inverted" constants more often, which is an aethetic
change to the IR but does permute some testcases.

Diff Detail

Event Timeline

lattner created this revision.Mar 19 2021, 9:22 PM
lattner requested review of this revision.Mar 19 2021, 9:22 PM

I was able to reproduce the valgrind errors with the original patch, and have verified that this fixes them. Thank you for reverting Alex!

lattner accepted this revision.Mar 20 2021, 4:30 PM

Accepting given that this was a previously reviewed patch.

This revision is now accepted and ready to land.Mar 20 2021, 4:30 PM