This is an archive of the discontinued LLVM Phabricator instance.

[StackProtector] Skip analysing dead users in HasAddressTaken, PR40436
AbandonedPublic

Authored by uabelho on Jan 24 2019, 5:23 AM.

Details

Reviewers
petpav01
mattd
rnk
Summary

The usual SSA rules don't apply for code that isn't reachable from the
entry, so we might find a user like

%user = select i1 %bool, i8* %ai, i8* %user

which is using itself, and then when examining that we would make
HasAddressTaken recurse until it blows the stack.

To determine if the user is in a basic block reachable from entry, we now
require that we have DominatorTree information. That affected a few test
cases checking the pass pipeline.

Diff Detail

Event Timeline

uabelho created this revision.Jan 24 2019, 5:23 AM

Not sure who should review this, I added the three last persons that I think did non-NFC changes to StackProtector.cpp.

Is this a proper way of solving the problem? Is it ok to require DT?

I like this patch, and I like the DominatorTree clean up/refactor. As you pointed out, your patch does make the DT required, which makes sense because your solution must make use of that analysis. I don't see that as an issue. Overall, this patch makes sense to me, but I'm curious as to what others think.

lib/CodeGen/StackProtector.cpp
161

s/laster/later/

rnk added a comment.Jan 24 2019, 11:14 AM

An alternative way to handle this would be to remove unreachable code. I'm surprised unreachable code reaches this pass in a normal pipeline. I thought CGP removed it in normal operation, even at O0. However, removing unreachable code might invalidate the domtree (unless our utility for that updates it?).

uabelho updated this revision to Diff 183483.Jan 24 2019, 10:23 PM

Fixed typo, reformulated a piece of a comment.

uabelho marked an inline comment as done.Jan 24 2019, 10:23 PM
In D57149#1369777, @rnk wrote:

An alternative way to handle this would be to remove unreachable code. I'm surprised unreachable code reaches this pass in a normal pipeline. I thought CGP removed it in normal operation, even at O0. However, removing unreachable code might invalidate the domtree (unless our utility for that updates it?).

An alternative that you would prefer?

I have to say that I think it makes sense that StackProtector can deal with the code on it's own since we never know when some dead code might reach StackProtector anyway, but perhaps there are strong reasons CGP really shouldn't leave dead code around?

I don't know CGP, but from the logs I see that it's after CGP that the dead blocks really get disconnected.
Before CGP:

*** IR Dump Before CodeGen Prepare ***
; Function Attrs: sspreq
define void @f1() #0 {
entry:
  %d = alloca i16, align 1
  br label %for.cond

for.cond:                                         ; preds = %for.cond, %entry
  br i1 true, label %for.cond, label %for.end

for.end:                                          ; preds = %for.cond
  %tobool = icmp ne i16 undef, 0
  br label %for.cond1

for.cond1:                                        ; preds = %for.body2, %for.end
  %d2 = phi i16* [ %spec.select, %for.body2 ], [ undef, %for.end ]
  br label %for.body2

for.body2:                                        ; preds = %for.cond1
  %spec.select = select i1 undef, i16* %d, i16* %d2
  br label %for.cond1
}

And then after:

*** IR Dump After CodeGen Prepare ***
; Function Attrs: sspreq
define void @f1() #0 {
entry:
  %d = alloca i16, align 1
  br label %for.cond

for.cond:                                         ; preds = %for.cond, %entry
  br label %for.cond

for.body2:                                        ; preds = %for.body2
  %spec.select = select i1 undef, i16* %d, i16* %spec.select
  br label %for.body2
}
uabelho updated this revision to Diff 185527.Feb 6 2019, 4:43 AM

Rebased.

Ping!

Is this ok or is it better to go down the CGP route instead? If so, can we really guarantee that all dead code is always removed when we get to StackProtector so we don't end up with this problem anyway?

uabelho updated this revision to Diff 185528.Feb 6 2019, 4:52 AM

Managed to drop the new testcase when I rebased >.<

mattd added a comment.Feb 6 2019, 10:28 AM

Hi @uabelho

The test case in your patch definitely causes a problem, but that's because the -start-before/-stop-after is used. If I run that same test through llc, the UnreachableBlockElim pass kicks-in and drops the dead code.
I took a look at the code in your Janurary 24th comment. I was unable to get the same dead block to surface, but most likely I had the wrong flag set. How did you build the sample in that comment?

Hi @uabelho

The test case in your patch definitely causes a problem, but that's because the -start-before/-stop-after is used. If I run that same test through llc, the UnreachableBlockElim pass kicks-in and drops the dead code.
I took a look at the code in your Janurary 24th comment. I was unable to get the same dead block to surface, but most likely I had the wrong flag set. How did you build the sample in that comment?

It can be reproduced with the full llc -O1 pipe on current trunk using:
llc -O1 -o - pr40436.ll

mattd added a comment.Feb 18 2019, 4:52 PM

Hi @uabelho

The test case in your patch definitely causes a problem, but that's because the -start-before/-stop-after is used. If I run that same test through llc, the UnreachableBlockElim pass kicks-in and drops the dead code.
I took a look at the code in your Janurary 24th comment. I was unable to get the same dead block to surface, but most likely I had the wrong flag set. How did you build the sample in that comment?

It can be reproduced with the full llc -O1 pipe on current trunk using:
llc -O1 -o - pr40436.ll

I was able to repro your issue. As pointed out earlier, CGP does not cover this particular case.
It might be useful to eliminate the dead code there, in CGP, if possible. At least we wouldn't be passing the unused statements around to other passes.
In any case I'd suggest tossing an assert in the StackProtector ensuring that such a the pathologic recursion does not occur.

I do see the point of ensuring the sanity of StackProtector, and I'm not opposed to patching that up (as you have done here in this patch); however, I do see benefit in preventing the dead code from reaching the StackProtector in the first place. I'm not sure how others feel.

I do see the point of ensuring the sanity of StackProtector, and I'm not opposed to patching that up (as you have done here in this patch); however, I do see benefit in preventing the dead code from reaching the StackProtector in the first place. I'm not sure how others feel.

To me there are two different issues.

  1. Fixing the immediate problem (in StackProtector)
  2. Doing optimizations, e.g. make CGP better in cleaning up the code.

My focus with this patch is to address 1, and if someone wants to do 2 and optimize CGP, then please go ahead with that too.

I didn't think fixing 1 would be controversial, apart from that possibly someone would have an opinion about the DT requirement.

In D57149#1369777, @rnk wrote:

An alternative way to handle this would be to remove unreachable code. I'm surprised unreachable code reaches this pass in a normal pipeline. I thought CGP removed it in normal operation, even at O0. However, removing unreachable code might invalidate the domtree (unless our utility for that updates it?).

I don't know CGP at all, but just from a quick look it seems like it doesn't require DT and it doesn't update it so I've no idea how messy it would be to go down that route.

There is some code in CodeGenPrepare::runOnFunction that tries to remove dead basic blocks, but those blocks are identified by having zero predecessors, so more complex situations with e.g. a loop that is unreachable from entry doesn't seem to be handled.

In this exact case the dead loop consists of several blocks from the beginning and then it's reduced down to

for.body2:                                        ; preds = %for.body2
  %spec.select = select i1 undef, i16* %d, i16* %spec.select
  br label %for.body2

by CodeGenPrepare::eliminateFallThrough but there doesn't seem to be anything after that tries to remove things.

uabelho abandoned this revision.Jun 12 2019, 11:04 PM

With r363169 the problem seems to be fixed, so this patch is probably not needed anymore.