This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Try to sink instructions into nearest common dominator of its users
AbandonedPublic

Authored by dmakogon on Sep 16 2022, 1:12 AM.

Details

Summary

Currently InstCombine would only sink instruction if all its users are in the same block and this is block is a successor of the current one.
There are cases where the users are in different blocks but all these blocks are dominated by succesor of our block.
E.g.:

%bb:
  %x = call i8* @foo()
  %is.null = icmp eq i8* %p, null
  br i1 %is.null, label %null, label %not.null

not.null:
  call void @use(i8* %x)
  br i1 %c, label %not.null.2, label %exit

not.null.2:
  call void @use(i8* %x)
  br label %exit

Here we could sink %x to not.null block.
This patch adjustes the InstCombine sinking mechanism so that it sinks instructions to the nearest common dominator of instruction users.

Diff Detail

Event Timeline

dmakogon created this revision.Sep 16 2022, 1:12 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 16 2022, 1:12 AM
dmakogon requested review of this revision.Sep 16 2022, 1:12 AM
nikic requested changes to this revision.Sep 16 2022, 2:04 AM

This has non-trivial compile-time impact: http://llvm-compile-time-tracker.com/compare.php?from=57c7bb3ec89565c68f858d316504668f9d214d59&to=aaee8dd0c8e1da698e87d7a62b23b4c3526a4a14&stat=instructions

The sinking functionality in InstCombine has always been something of a hack in that it is largely orthogonal to InstCombine's core purpose. It is only acceptable as long as it is reasonably cheap. If you want support for something that goes beyond "trivial" sinking, then that must go into a dedicated sinking pass (which does not have to suffer from other InstCombine sinking limitations either).

We may be able to consider this if the implementation can be changed to be essentially free. The used implementation approach is fairly weird in that InstCombine will only sink into a direct successor of the block (ignoring terminator blocks for now). So this spends effort computing an NCD and will then only sink into it if it happens to be a successor of BB with a unique predecessor. However, the fact that it is an NCD is not actually relevant, we can sink into any dominating block. So a possible alternative approach is to find out a) whether there is any unique predecessor successor of BB that dominates the first use and b) that successor also dominates all the other uses. I don't know if that will help, but it might (it will also allow sinking in more cases.)

This revision now requires changes to proceed.Sep 16 2022, 2:04 AM
dmakogon abandoned this revision.Nov 14 2022, 4:14 AM