This is an archive of the discontinued LLVM Phabricator instance.

[SimplifyCFG] Fix inconsistency in block size assessment for threading
ClosedPublic

Authored by mkazantsev on Jun 15 2020, 3:43 AM.

Details

Summary

Sometimes SimplifyCFG may decide to perform jump threading. In order
to do it, it follows the following algorithm:

  1. Checks if the block is small enough for threading;
  2. If yes, inserts a PR Phi relying that the next iteration will remove it by performing jump threading;
  3. The next iteration checks the block again and performs the threading.

This logic has a corner case: inserting the PR Phi increases block's size
by 1. If the block size at first check was max possible, one more Phi will
exceed this size, and we will neither perform threading nor remove the
created Phi node. As result, we will end up with worse IR than before.

This patch fixes this situation by excluding Phis from block size computation.
Excluding Phis from size computation for threading also makes sense by
itself because in case of threadign all those Phis will be removed.

Diff Detail

Event Timeline

mkazantsev created this revision.Jun 15 2020, 3:43 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 15 2020, 3:43 AM

clang-format

xbolva00 added inline comments.Jun 15 2020, 3:57 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2199

Skip llvm.assume too?

nikic added a subscriber: nikic.Jun 15 2020, 4:02 AM
nikic added inline comments.
llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll
17

This test should be adjusted with extra store -1 to retain the previous behavior, otherwise it doesn't show what it's supposed to be showing.

mkazantsev marked 2 inline comments as done.Jun 16 2020, 1:58 AM
mkazantsev added inline comments.
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2199

Not sure if it makes sense, given that this restriction's point (or at least one of them) is to save compile time.

llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll
17

Ok.

Fixed test.

mkazantsev edited the summary of this revision. (Show Details)
mkazantsev edited the summary of this revision. (Show Details)
asbirlea accepted this revision.Jun 29 2020, 11:54 AM

LGTM, but please wait to see if nikic@ has additional comments.

This revision is now accepted and ready to land.Jun 29 2020, 11:54 AM
nikic accepted this revision.Jun 29 2020, 12:22 PM

LG as well. The phis are a threading opportunity, not a cost.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2198

This comment is a bit confusing to me. I would reason the other way around here and say "We will delete Phis while threading, so Phis should not be accounted in block's size".

llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll
17

The changes in this test will probably have gone away due to a change to alignment assumptions that has landed in the meantime.

mkazantsev closed this revision.Jun 29 2020, 11:01 PM
commit f01d9e6fc3e291a2faed8c9b7dcbabf760f32bd6
Author: Max Kazantsev <mkazantsev@azul.com>
Date:   Tue Jun 30 12:38:15 2020 +0700

    [SimplifyCFG] Fix inconsistency in block size assessment for threading

    Sometimes SimplifyCFG may decide to perform jump threading. In order
    to do it, it follows the following algorithm:

    1. Checks if the block is small enough for threading;
    2. If yes, inserts a PR Phi relying that the next iteration will remove it
       by performing jump threading;
    3. The next iteration checks the block again and performs the threading.

    This logic has a corner case: inserting the PR Phi increases block's size
    by 1. If the block size at first check was max possible, one more Phi will
    exceed this size, and we will neither perform threading nor remove the
    created Phi node. As result, we will end up with worse IR than before.

    This patch fixes this situation by excluding Phis from block size computation.
    Excluding Phis from size computation for threading also makes sense by
    itself because in case of threadign all those Phis will be removed.

    Differential Revision: https://reviews.llvm.org/D81835
    Reviewed By: asbirlea, nikic