Page MenuHomePhabricator

[InstCombine] Improve TryToSink for side-effecting calls that would be trivially dead
Needs ReviewPublic

Authored by anna on Sep 16 2021, 1:19 PM.

Details

Summary

This patch adds support to sink side-effecting calls that are legal to
sink to the successor use block. We can sink such calls as long as these
two conditions are satisfied:

  1. The instruction would be trivially dead (i.e. if there were no uses of the instruction, we can remove the instruction).
  2. There are no side-effecting instructions between the current one until the end of the block.

This helps with sinking allocations down to use blocks when safe to do
so (see added testcases).

Diff Detail

Event Timeline

anna created this revision.Sep 16 2021, 1:19 PM
anna requested review of this revision.Sep 16 2021, 1:19 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 16 2021, 1:19 PM
mkazantsev added inline comments.Sep 23 2021, 11:08 PM
llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
3695

What if I has implicit control flow, e.g. may call system exit?

anna added inline comments.Sep 27 2021, 6:42 AM
llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
3695

So, after this transform, we would have some non side-effecting instructions that are executed before this I that may call system exit. Why would this matter?

Note that if we were moving this instruction past some side-effecting (example not marked willreturn), there is a problem. But that isn't the case here.

Skimming the code for this and the prerequisite patch, I'm a bit uncomfortable. It really feels like you're trying to a) do several things in one change, and b) possibly abusing an interface for a purpose it wasn't intended.

I would suggest moving the no-alias-call bit to a separate patch as that seems unrelated to the core functionality.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
3745

Hm, I am not sure here, but I think you should check for potential reads here as well.

My reasoning is as follows. While the instruction we're moving might be trivially dead if there are no users, it may *not* be trivially dead if there are users. There may be some externally arranged invariant that (say) the result is stored with a volatile variable *if-and-only-if* the call actually has a side effect.

As an example, consider the following:
a = malloc()
stat = malloc_library_counter()
if (c)

free(a)

Basically, is it legal to sink the malloc in this case? I legitimately don't know what the right answer is here.

Another example might be:
a = malloc()
stat = malloc_library_counter()
if (c)

(volatile i8*)g = a;
reames added inline comments.Sep 28 2021, 9:57 AM
llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
3745

JFYI, my potential cases just described are definitely disallowed by the function comment in the header which describes trivial-deadness. Unfortunately, so is malloc. As such, that comment is definitely wrong, and needs updated. :)

anna added a comment.Sep 30 2021, 8:54 AM

Skimming the code for this and the prerequisite patch, I'm a bit uncomfortable. It really feels like you're trying to a) do several things in one change, and b) possibly abusing an interface for a purpose it wasn't intended.

For others following along: we plan to discuss offline. Will summarize result.

I would suggest moving the no-alias-call bit to a separate patch as that seems unrelated to the core functionality.

Unfortunately, the no-alias bit is required for the malloc, since the Scan instruction *starts* from the instruction we try to sink (i.e. the malloc call) and we fail at mayWriteToMemory. We can frame this as possibly a CT win and land it separately.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
3745

I'm not sure if trivial-deadness is the property used in DSE for removing the malloc, but the case above is handled by DSE even if we have an externally arranged invariant through malloc_library_counter for example:

cat simple.ll

declare noalias i8* @malloc(i32) willreturn
declare i32 @malloc_library_counter()
define void @test20A() {
  %m = call i8* @malloc(i32 24) 
   %stat = call i32 @malloc_library_counter()
   store i8 0, i8* %m
   ret void
}

` opt -basic-aa -dse -S simple.ll` :

define void @test20A() {

%stat = call i32 @malloc_library_counter()
ret void

}

anna planned changes to this revision.Oct 1 2021, 7:05 AM

Had an offline discussion with Philip. Plan to separate out two APIs showing the difference between "isTriviallyDeadOnAllPaths" versus "isTriviallyDeadOnSomePaths".

anna updated this revision to Diff 390089.Fri, Nov 26, 9:49 AM

separated out API