This is an archive of the discontinued LLVM Phabricator instance.

[DSE] Translate killing locations through phis.
Needs ReviewPublic

Authored by fhahn on Mar 9 2021, 12:57 PM.

Details

Summary

This patch updates DSE to translate the address of the killing access
through phis when traversing MemoryPhis. Note that this still misses
cases where we could translate phis, but there are no MemoryPhis in the
block with the translatable phi.

This is an initial step to improve DSE in the presence of address phis.
It can be improved in the future to also do phi translation when
stepping over any type of access, not just MemoryPhis. There's also a
related patch D90095.

Diff Detail

Event Timeline

fhahn created this revision.Mar 9 2021, 12:57 PM
fhahn requested review of this revision.Mar 9 2021, 12:57 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 9 2021, 12:57 PM
ebrevnov added inline comments.Mar 11 2021, 1:33 AM
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1954

Are you sure 32 is good default? Maybe just not to set it?

1966

Why do you need that?

1971

My understanding is the third parameter of getDomMemoryDef should be location of killing store. Changing it to phi translated one seems problematic.

2003

Addr is expected to be non null if successfully translated. Turn into assert?

In general this patch seems to take exactly the same direction as D90095 and is a strict subset of it. We can choose to either re-build functionality step by step or take D90095 and split it to several smaller pieces. D90095 adds the follwoing functionality:

  1. Replaces main 'do-while' loop to 'for' loop in getDomMemoryDef. This is NFC and aimed at simplifying code structure and allows to minimize future changes.
  2. Supports phi translation to any predecessor (not only immediate one)
  3. Is able to phi translate in presence of geps and casts. In order to support this we have to track offests.

Please let me know which way you prefer to go.

I'm seeing a crash with this. Repro: opt -passes=dse on:

%"struct.type" = type <{ i8 }>

; Function Attrs: noreturn
define void @f() {
entry:
  br label %while.cond

while.cond:                                       ; preds = %exit, %entry
  br i1 undef, label %if.end.i, label %if.then.i

if.then.i:                                        ; preds = %while.cond
  br label %exit

if.end.i:                                         ; preds = %while.cond
  store i8* undef, i8** inttoptr (i64 16 to i8**), align 16
  %.cast1.i = bitcast i8* undef to %"struct.type"*
  %IsMemberPointer.i.i = getelementptr inbounds %"struct.type", %"struct.type"* %.cast1.i, i64 0, i32 0
  store i8 0, i8* %IsMemberPointer.i.i, align 4
  br label %exit

exit: ; preds = %if.end.i, %if.then.i
  %retval.0.i = phi %"struct.type"* [ undef, %if.then.i ], [ %.cast1.i, %if.end.i ]
  %IsMemberPointer = getelementptr inbounds %"struct.type", %"struct.type"* %retval.0.i, i64 0, i32 0
  store i8 1, i8* %IsMemberPointer, align 4
  br label %while.cond
}
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1945–1946

Current unused in release builds.

fhahn added a comment.Apr 7 2021, 6:04 AM

In general this patch seems to take exactly the same direction as D90095 and is a strict subset of it. We can choose to either re-build functionality step by step or take D90095 and split it to several smaller pieces. D90095 adds the follwoing functionality:

  1. Replaces main 'do-while' loop to 'for' loop in getDomMemoryDef. This is NFC and aimed at simplifying code structure and allows to minimize future changes.
  2. Supports phi translation to any predecessor (not only immediate one)
  3. Is able to phi translate in presence of geps and casts. In order to support this we have to track offests.

Please let me know which way you prefer to go.

Now that this code is enabled by default (and the legacy implementation has gone away), I think we try to proceed in small steps if possible to keep things as stable as possible, because subtle correctness issues may remain dormant for a while.

If you'd be happy to break up your patch, that sounds great. I think the missing features (2. and 3. above) at least should be separate patches, with independent evaluation of the benefits & trade-offs. It might still make sense to start with the current patch as initial starting point and add functionality from D90095 step-by-step.

I'm seeing a crash with this. Repro: opt -passes=dse on:

Is it possible you did not apply the dependent patch D98287 as well? Without this patch, I see a crash with the example you shared, but with D98287 I do not see a crash.

fhahn updated this revision to Diff 354965.Jun 28 2021, 11:42 AM

Addressed outstanding comments & rebased

fhahn updated this revision to Diff 354967.Jun 28 2021, 11:45 AM
fhahn marked 3 inline comments as done.

remove manual size from ToCheck declaration.

fhahn updated this revision to Diff 354968.Jun 28 2021, 11:46 AM

Remove Current variable, which was only used in LLVM_DEBUG.

fhahn marked an inline comment as done.Jun 28 2021, 11:46 AM
fhahn added inline comments.
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1945–1946

thanks, I removed the variable.

1954

Thanks, I went ahead and removed it.

1966

It's not needed in the latest version. I removed it. Thanks!

1971

The location is used to find a potentially dead store. We should already have checked all candidates after the phi, so I don't think we would miss any candidates after translating. And when scanning for reads, AA should be conservative when dealing with the translated location. Is there anything in particular you think could be problematic?

2003

good point, done!

vdsered added a subscriber: vdsered.Jul 9 2021, 9:22 AM
vdsered added inline comments.
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1999

Why do we need to check if IncomingBlock is in a set of predecessors of PhiBlock? Isn't it always true? I thought there could probably be a reason like PhiBlock points to itself, but it seems that I'm wrong because we shouldn't get here in that case as we forbid it by the if-statement

if (State.PostOrderNumbers[IncomingBlock] >
              State.PostOrderNumbers[PhiBlock])

don't we?

vdsered added inline comments.Jul 9 2021, 9:23 AM
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1999

*A little correction*
I meant that there could be a reason to check this if PhiBlock == IncomingBlock