Details
Diff Detail
- Repository
- rL LLVM
Event Timeline
This is not safe to do.
LLVM's basic blocks are really closer to EBB's.
You can't assume the only place it will return false is at a terminator. It can and will return false for calls in the middle of the block, for example.
I agree. Still I think there is a bug in isGuaranteedToTransferExecutionToSuccessor. What if there is a basic block like this with only an unreachable instruction.
exit: unreachable
In this case isGuaranteedToTransferExecutionToSuccessor should return false for the unreachable instruction.
Sure, and if you want to fix that bug, i think it's worth doing. But i think that's not related to fixing any gvnhoist problem :P
Thanks, I'm working on your remarks on gvn-hoist. Please accept the patch if this looks reasonable.
I think this patch is correct but unnecessary. It is papering over an issue in GVNHoist. @efriedma - what do you think?
| llvm/trunk/lib/Analysis/ValueTracking.cpp | ||
|---|---|---|
| 3784 | This looks fishy to me, returning true from here for unreachable should also be fine (i.e. both true and false are correct answers). The rule for unreachable is that executing it generates undefined behavior, so you're allowed to pretend it never executed, which in turn means the client calling this code should be allowed to pretend that it indeed is "guaranteed" to transfer control to any place in the CFG. For instance, if the test case for 32153 would have been: define void @test_command(i32 %c1) {
entry:
switch i32 %c1, label %exit [
i32 0, label %sw0
i32 1, label %sw1
]
sw0:
store i32 1, i32* @G
br label %exit
sw1:
store i32 1, i32* @G
br label %exit
exit:
unreachable
}then hoisting the store to @G would have been fine. The only place path on which @G is not stored to has undefined behavior. The actual bug is that, as @dberlin said, GVNHoist needs to call isGuaranteedToTransferExecutionToSuccessor on every instruction, not just terminators. | |
| llvm/trunk/lib/Analysis/ValueTracking.cpp | ||
|---|---|---|
| 3784 | Hmmm. | |
This is definitely papering over the problem; for example, take the given testcase, and replace the "unreachable" with "br label %exit".
I would say it makes more sense to return false, as opposed to true... but only because there aren't any successors to transfer execution to.
Right.
The only reason i approve it is because we currently say "nothing" about unreachable, and i felt we should say *something*.
As i said earlier, gvnhoist is clearly broken either way.
I would say it makes more sense to return false, as opposed to true... but only because there aren't any successors to transfer execution to.
Thinking harder about it, i'm pretty sure if we answer true we get wrong answers in some cases. But they may not matter.
For example, it would make us think, in some cases, it is okay to sink things from reachable parts to past the unreachable, no?
But it's really not.
My gut feeling is it's possible to create a case where we do the wrong thing (IE turn defined behavior into undefined behavior), but perhaps we aren't that clever.
Staring at other places it is used, it looks like it would also think it okay to propagate various non-nullness attributes, etc past unreachable.
That looks more innocuous, at least at a glance.
Staring at other places it is used, it looks like it would also think it okay to propagate various non-nullness attributes, etc past unreachable.
Propagate them to where? unreachable doesn't have any successors. This only makes sense if you connect the unreachable to the function's exit, or something like that.
Backwards:
for (Instruction &I : Entry) {
if (auto CS = CallSite(&I)) {
if (auto *CalledFunc = CS.getCalledFunction()) {
for (auto &CSArg : CalledFunc->args()) {
if (!CSArg.hasNonNullAttr())
continue;
// If the non-null callsite argument operand is an argument to 'F'
// (the caller) and the call is guaranteed to execute, then the value
// must be non-null throughout 'F'.
auto *FArg = dyn_cast<Argument>(CS.getArgOperand(CSArg.getArgNo()));
if (FArg && !FArg->hasNonNullAttr()) {
FArg->addAttr(Attribute::NonNull);
Changed = true;
}
}
}
}
if (!isGuaranteedToTransferExecutionToSuccessor(&I))
break;
}IE the case i'm thinking of, but not sure if we care about:
If there are calls in the entry block, and the entry block ends in unreachable, we have the property that the unreachable means we can assume the block doesn't execute.
But we are still using the calls in the block pretending that they are guaranteed to execute.
:)
IE I was told the semantics of unreachable say that if we are guaranteed to hit the unreachable, along a given codepath, we can assume that code path cannot execute.
So should we be propagating non-nullness based on them?
If you have a function like this:
define void @f(i32* %z) { unreachable }
We can mark %z nonnull because there's a nonnull assumption along every feasible path. I'm not sure what that has to do with this patch, though.
There is? We could propagate the unreachableness of this function to its callsites, but I don't see what that has to do with the value of the function argument.
...
IE I was told the semantics of unreachable say that if we are guaranteed to hit the unreachable, along a given codepath, we can assume that code path cannot execute.
This is my understanding as well.
There is? We could propagate the unreachableness of this function to its callsites, but I don't see what that has to do with the value of the function argument.
LangRef states "This indicates that the parameter or return pointer is not null", i.e. if the parameter is null, the function has undefined behavior. The function in my example always has undefined behavior, therefore it has undefined behavior if you call it with a null pointer, therefore you can mark the parameter nonnull.
Okay, so to close this out, what would we like to do about isGuaranteedToTransferExecutionToSuccessor?
Continue have it return false?
Past that, it's clear additional bugs should be filed against gvnhoist.
My inclination would be to have it explicitly (with a nice comment) return true. That would make bugs like the GVNHoist one we're talking about here more obviously buggy.
In the same function isGuaranteedToTransferExecutionToSuccessor, line: ~3783, there is a comment.
// If there is no successor, then execution can't transfer to it. if (const auto *CRI = dyn_cast<CleanupReturnInst>(I)) return !CRI->unwindsToCaller();
Since a basic block with unreachable instruction will not have any successor, shouldn't it follow the same logic. I agree that in the example that you gave it would be better if gvnhoist would hoist the instruction, and there is a bug in gvnhoist (that I'm working on to fix), but isGuaranteedToTransferExecutionToSuccessor is called from other places as well.
This looks fishy to me, returning true from here for unreachable should also be fine (i.e. both true and false are correct answers). The rule for unreachable is that executing it generates undefined behavior, so you're allowed to pretend it never executed, which in turn means the client calling this code should be allowed to pretend that it indeed is "guaranteed" to transfer control to any place in the CFG.
For instance, if the test case for 32153 would have been:
define void @test_command(i32 %c1) { entry: switch i32 %c1, label %exit [ i32 0, label %sw0 i32 1, label %sw1 ] sw0: store i32 1, i32* @G br label %exit sw1: store i32 1, i32* @G br label %exit exit: unreachable }then hoisting the store to @G would have been fine. The only place path on which @G is not stored to has undefined behavior.
The actual bug is that, as @dberlin said, GVNHoist needs to call isGuaranteedToTransferExecutionToSuccessor on every instruction, not just terminators.