cmm/CBE: Collapse blocks equivalent up to alpha renaming of local registers

Authored by bgamari on Sep 15 2017, 10:07 AM.



As noted in Trac #14226, the common block elimination pass currently implements an
extremely strict equivalence relation, demanding that two blocks are equivalent
including the names of their local registers. This is quite restrictive and
severely hampers the effectiveness of the pass.

Here we allow the CBE pass to collapse blocks which are equivalent up to alpha
renaming of locally-bound local registers. This is completely safe and catches
many more duplicate blocks.

Test Plan


Diff Detail

rGHC Glasgow Haskell Compiler
Automatic diff as part of commit; lint not applicable.
Automatic diff as part of commit; unit tests not applicable.
bgamari created this revision.Sep 15 2017, 10:07 AM
michalt requested changes to this revision.Sep 16 2017, 10:40 AM



I'd move the comment to the place where we AND with 0x7fffffff
(I wonder if this still a problem)


Nit: remove whitespace after (


Hmm.. Shouldn't we apply the LocalRegMapping also to the expressions in the last node? I could imagine a conditional branch where the condition mentions one of the local variables.


This is unrelated to your change, but do we compare the length of nodes and nodes' anywhere? If not, it seems it would be possible to ignore some node that, e.g., modifies a global register.

This revision now requires changes to proceed.Sep 16 2017, 10:40 AM
bgamari marked 4 inline comments as done.Sep 16 2017, 11:00 PM
bgamari added inline comments.

Whoops, good catch.


Great point. I've fixed this and your next comment in the new version.

bgamari updated this revision to Diff 13939.Sep 16 2017, 11:01 PM
bgamari edited edge metadata.
bgamari marked 2 inline comments as done.

Address @michalt's comments

bgamari updated this revision to Diff 13940.Sep 16 2017, 11:05 PM
bgamari marked an inline comment as done.

A bit of reformatting

michalt added inline comments.Sep 17 2017, 7:27 AM

Did you mean equal_go? (I don't see any equal_mid)


I might be missing something but this doesn't seem to help with different lengths of lists. If I have [CmmAssign] and []:

  • The first pattern checks for heads of both lists, so it won't match.
  • The second pattern checks for both lists being empty, so it won't match.
  • The last pattern only looks at the terminator node.

Maybe something like

equal_go _ (_:_) [] = False
equal_go _ [] (_:_) = False
bgamari updated this revision to Diff 13956.Sep 18 2017, 4:10 PM

Fix silly mistake


Silly me; this is what happens when you try to sneak in a bit of coding before leaving for a hike. I had the terminal and non-equal cases mixed up. Perhaps this looks more reasonable?

michalt accepted this revision.Sep 19 2017, 3:12 PM
This revision is now accepted and ready to land.Sep 19 2017, 3:12 PM
This revision was automatically updated to reflect the committed changes.