This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Remove trivially empty ranges from end
ClosedPublic

Authored by nikic on Feb 22 2020, 9:46 AM.

Details

Summary

InstCombine removes pairs of start+end intrinsics that don't have anything in between them. Currently this is done by starting at the start intrinsic and scanning forwards. This patch changes it to start at the end intrinsic and scan backwards.

The motivation here is as follows: When we process the start intrinsic, we have not yet looked at the following instructions, which may still get folded/removed. If they do, we will only be able to remove the start/end pair on the next iteration. When we process the end intrinsic, all the instructions before it have already been visited, and we don't run into this problem.

The highlighted test case drops from 4 to 2 iterations, because we can pick up all four start/end pairs in one pass, instead of doing one on each iteration.

Diff Detail

Event Timeline

nikic created this revision.Feb 22 2020, 9:46 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 22 2020, 9:46 AM
nikic updated this revision to Diff 246085.Feb 22 2020, 11:17 AM

Handle interleaving of start/end intrinsics with different args better. This reduces iterations on the lifetime.ll test.

Nice. Makes me wonder what other loops in clang would work better backwards :-)

spatel added inline comments.Feb 26 2020, 6:10 AM
llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
1482

Add a comment to explain why we're using the end instruction and reverse_iterator (can copy/adapt text from this patch description).

1488–1489

Is there a logic change from 'if &&' to 'if, if ...continue'? If so, that deserves a code comment.

If it's just a matter of taste, it would be better to make that + a partial function signature change as a preliminary NFC commit. (Trying to limit patch risk here because I'm not very familiar with these transforms.)

nikic updated this revision to Diff 246754.Feb 26 2020, 8:55 AM

Add comments.

nikic marked 2 inline comments as done.Feb 26 2020, 9:01 AM
nikic added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
1488–1489

There is a logic change: This skips start intrinsics that don't pair with the end intrinsic (I've added a comment to that effect below).

This doesn't affect the final behavior (due to the existing skipping for the end intrinsic), but avoids doing extra iterations, for example:

start(0) <- erase
start(1) <- skip
end(0) <- I
end(1)

Without this change, we'd not do anything for end(0), but then

start(0)
start(1) <- erase
end(0) <- skip
end(1) <- I

and would collect end(0) on the next InstCombine iteration.

spatel accepted this revision.Feb 26 2020, 9:41 AM

LGTM

This revision is now accepted and ready to land.Feb 26 2020, 9:41 AM
This revision was automatically updated to reflect the committed changes.