Details
Diff Detail
- Repository
- rL LLVM
Event Timeline
| llvm/test/Transforms/GVNHoist/hoist-unsafe-pr31729.ll | ||
|---|---|---|
| 3–6 ↗ | (On Diff #85612) | How does this test work? If this is about hoisting wouldn't we always see 3 urem instructions no matter if we did the hoisting or not? |
| llvm/test/Transforms/GVNHoist/hoist-unsafe-pr31729.ll | ||
|---|---|---|
| 3–6 ↗ | (On Diff #85612) | If urem is hoisted, then there will be only two urem. It can be verified by running this test without the patch. |
| llvm/lib/Transforms/Scalar/GVNHoist.cpp | ||
|---|---|---|
| 510 ↗ | (On Diff #85612) | GVNHoist already has facilities to check the dependencies, safety etc. which is more efficient than calling isSafeToSpeculativelyExecute all the time for each instruction. |
The test can probably be further simplified by removing unnecessary information:
- datalayout, sourcefilename, modulename
- TBAA metadata
- ; preds comments
- the "all good" string
...
| llvm/lib/Transforms/Scalar/GVNHoist.cpp | ||
|---|---|---|
| 510 ↗ | (On Diff #85612) | Sounds like at least an assert(isSafeToSpeculativelyExecute()); is a good idea. |
Fixed the test case. Also it is not possible to put assert isSafeToSpeculativelyExecute because it does not handle all the cases like call.
Ping for David, does this look good to you now?
As this is an obvious miscompile I'd like to get the patch into 4.0.
I think Aditya has addressed the review comments from David.
David, do you see something else in the current patch that requires changes?
David, do you have any further concerns? Otherwise I'd like to see this committed so we can resolve the PR for 4.0.
I don't understand why we cannot assert isSafeToSpeculativelyExecute if we are not in minsize. If we are given a call instruction, why do we think it is safe to hoist it?
| llvm/lib/Transforms/Scalar/GVNHoist.cpp | ||
|---|---|---|
| 510 ↗ | (On Diff #85612) | The function name is safeToHoistScalar, I don't understand why OptForMinSize is checked at all here. There shouldn't be *any* profitability involved in this function, according to its name and its description. |
So it seems that GVN-hoist tries to be "smarter" and hoist things for which isSafeToSpeculativelyExecute is returning false.
This is a nice aggressive optimization, but if it isn't safe (it seems it is not right now considering there are bugs in 4.0), we should *disable* this behavior in clang-4.0 and GVN-hoist should rely *only* on isSafeToSpeculativelyExecute as a legality criteria.
I'd add also that isSafeToSpeculativelyExecute may be conservative right now, but it should improve with https://reviews.llvm.org/D20116
So it is even unclear to me which cases GVN hoist would be able to catch that are not in the realm of isSafeToSpeculativelyExecute.
I don't understand why we cannot assert isSafeToSpeculativelyExecute if we are not in minsize. If we are given a call instruction, why do we think it is safe to hoist it?
It's safe to hoist if the instruction is either speculatable, or executed on all paths. (Consider, for example, "if (x) { f(a/b); } else { g(a/b); }", where b might be zero.)
I am also no longer convinced the current fix is correct. Obviously memory SSA does not deal with all side effects necessary for the Div instruction or we wouldn't need this fix at all. I don't know whether that is by in the sense that memory SSA only deals with memory or if it should be considered a bug in memory SSA. In any case being conservative here in the face of bugs sounds like the right thing.
Please mention http://llvm.org/PR31729 in the commit message.
So if you have a readnone function with a division inside that could potentially fail, this will work correctly and not hoist it?
No.
Please read the review I linked that introduce a new attribute to this end, because not having *memory* side effects is not enough.
Currently isSafeToSpeculativelyExecute returns false for Calls, stores. GVN Hoist will hoist them if it is legal to do so.
Can you address everything of what I wrote please instead of repeating partially what I wrote? I don't feel we'll make progress here.
The concern is precisely that it does not do so correctly.
In fact, it definitely does not.
As a trivial example: Nowhere, does GVNHoist check for whether calls unwind or not.
It checks for "EH on a path", but it doesn't check this, for example.
Now, actually, i do not believe isSafeToSpeculativelyExecute is the right answer here longer term, because it is easy to do better than it.
But you at least must be as correct as it.
(Though i quibble with this part:
The called function could have undefined behavior or
side-effects, even if marked readnone nounwind.
I'm not sure what we think those side effects are, but we should be modeling them or ignoring them.
)
The thing that is hard to crasp here: If gvn hoist catches all that, why do we need to add the check in the minsize case at all? Why would those mechanisms only fail for OptSize?
MemorySSA deliberately deals with memory.
It does not care about other side-effects, nor should it.
Attempts to try to capture random side effects inside side-irs is ... often quite a mess. This is because it is usually a complete guess at what the client is looking for.
It gives completely correct answer to what memory is used by what. That's all it does.
(That's also all memdep does).
Divide by zero?
The only current solution we have for this now is to be conservative with respect to calls. There is a new attribute implemented here https://reviews.llvm.org/D20116 that will help making it "less conservative", by allowing to speculate if there can't be UB whatever arguments are passed to the function.
This wouldn't capture this for instance:
// can be speculated if we know that the argument is never 0
int inverse(int n) { return 1/n; }From your GCC experience, do you have a suggestion how to address/model this?
It will not hoist because the execution of function has to be present on all path from the hoisting point to all the leaf BasicBlocks. For example
int foo(int i, int j) {
return i/j;
}
if (j != 0)
foo(i, j)will not get hoisted because the function foo is present only on one patch from hoisting point (one of the common dominators of if-block) to the leaf basic blocks. It will get hoisted in this case however:
int foo(int i, int j) {
return i/j;
}
if (j != 0)
foo(i, j);
else
foo(i, j)But in this case the original code is going to fail as well. Please correct me if I'm missing something.
GVNHoist: 935 checks if Call->mayThrow() which checks if the call will unwind or not IIUC.
Thanks for the feedback.
There are two ways you can prove hoisting an instruction doesn't introduce undefined behavior.
One is isSafeToSpeculativelyExecute. This is obvious and uncontroversial.
The other involves proving that if the hoisted instruction has undefined behavior, the program's behavior was undefined anyway. For example, consider "if (x) { f(a/b); } else { g(a/b); }". You can hoist a/b out of the if statement because if b is zero, you hit undefined behavior on either path. Proving safety here is tricky; there are a lot of edge cases you need to deal with to get this right. For example, you need to check individual instructions with isGuaranteedToTransferExecutionToSuccessor, and you need to handle potentially infinite loops. (It's possible we could improve the IR to make this easier; see the discussion on https://reviews.llvm.org/D21041 .)
GVNHoist on trunk just blindly hoists anything, without trying to prove either condition. This isn't causing real-world issues outside of OptForMinSize mode because, in an unrelated check, GVNHoist doesn't hoist anything past calls which write to memory.
I'm sorry I was in the middle of replying you when your message came, that's why it was a partial reply.
With the link you shared, IIUC, that only addresses the call instructions and only when the attribute 'speculatable' is present. This will stop hoisting of call instructions which does not have that attribute even if it is legal to hoist them.
For example:
int foo(int *i) {
return *i;
}
bar() {
int *ptr;
if (cond)
foo(ptr);
else
foo(ptr);
}Well, i don't believe this is quite true.
I believe instead, the checks are hidden and a complete mess, such that it's not obvious that it's either correct or complete.
GVNHoist: 935 checks if Call->mayThrow() which checks if the call will unwind or not IIUC.
mayThrow() isn't really helpful here; consider:
#include <stdlib.h>
void f() { exit(0); }
void (*ff)() = f;
int r;
int g(int x, int a) {
if (a) {
r = 999 / x;
return 3;
} else {
ff();
return 999 / x;
}
}
int (*gg)(int, int) = g;
int main() {
gg(0, 0);
}Thanks for the feedback. GVNHoist does that. Please see the GVNHoist:298 hoistingFromAllPaths(). It will hoist instructions only when they are very busy. Only in the case of '-Os' the check was removed from scalars which introduced this bug. So I added
the check isSafeToSpeculativelyExecute to bail out quickly in this case by being conservative.
Proving safety here is tricky; there are a lot of edge cases you need to deal with to get this right. For example, you need to check individual instructions with isGuaranteedToTransferExecutionToSuccessor, and you need to handle potentially infinite loops. (It's possible we could improve the IR to make this easier; see the discussion on https://reviews.llvm.org/D21041 .)
GVNHoist on trunk just blindly hoists anything, without trying to prove either condition. This isn't causing real-world issues outside of OptForMinSize mode because, in an unrelated check, GVNHoist doesn't hoist anything past calls which write to memory.
First:
int __attribute__((noinline)) inverse(int n) { return 1/n; }
int main(int argc)
{
int a = 0;
for (int i = 0; i < 5; ++i)
a+= inverse(argc);
return 0
}Is optimized to return 0 at all opt levels (ie it does not consider it enough of a side effect to keep it alive)
(it's the same whether it's inlined or not)
If you change it to return a, you get:
main (int argc)
{
int i;
int a;
int _16;
_16 = inverse (argc_5(D));
# a_14 = PHI <a_7(3), 0(2)>
# i_15 = PHI <i_8(3), 0(2)>
a_7 = a_14 + _16;
i_8 = i_15 + 1;
if (i_8 != 5)
goto <bb 3>;
else
goto <bb 4>;
return a_7;
}Note the hoist.
It then unrolls the loop
resulting in:
main (int argc)
{
int a;
int _16;
_16 = inverse (argc_5(D));
a_2 = _16 * 5;
return a_2;
}If you change it to something it can't prove always executes, it still hoists it to the pre-header, just not above loop condition (obviously).
So i guess my answer is: We are being too conservative here.
Thanks for the feedback. GVNHoist does that. Please see the GVNHoist:298 hoistingFromAllPaths(). It will hoist instructions only when they are very busy.
Oh, okay. That's... the right sort of thing, but I think it's missing some checks. The most obvious hole is that you need to call isGuaranteedToTransferExecutionToSuccessor on each instruction in the block, not just the terminator. It also looks like it doesn't handle infinite loops correctly.
Gcc eliminates/hoist this one too if you make the function pointer local, or compile in whole-program mode.
GVNHoist only hoists hings executed on all paths, it does not create executions on paths they were not executed on before.
Thus, it will have precisely the same behavior as gcc .
At least, if implemented correctly.
See https://reviews.llvm.org/D8688#a1aa52c6
computeBarriers, for a way to compute the barriers once and be able to constant time check whether they are in the way.
(since you have dfs numbers for the instructions)
| llvm/lib/Transforms/Scalar/GVNHoist.cpp | ||
|---|---|---|
| 510 ↗ | (On Diff #85612) | I agree, I can put this check outside if the function safeToHoistScalar, it is seems more reasonable. |
It checks for Branches with isGuaranteedToTransferExecutionToSuccessor, other than that there are memory instructions and calls in the definition of isGuaranteedToTransferExecutionToSuccessor, which are handled separately (with some help from MemorySSA) here. So there is no need to call this function for each instruction.
Can you please clearly map for us the things that function checks for to where you are doing it here?
Literally, i mean?
Honestly, i think a large amount of the commentary on this review would have been avoided with clear, concise, and centralized code that mapped existing and well known idioms for doing these things in llvm into the way you achieve the same result.
Since gcc's gvn hoist works in tandem with gvn-pre, the hoist of a call which occurs only on one branch may have been done by gvn-pre. IIUC gcc's gvn-hoist only hoists instructions which are anticipable (IN) but not available (OUT), that too with basic blocks with > 1 successors (ref: gcc/tree-ssa-pre.c:3499). It is unlikely gvn-hoist is hoisting the call in this example. Another limitation of gcc's gvn-hoist is that it only hoists when at least one immediate successor has the instruction in avail_out. So even if an expression is very busy it may not get hoisted. I understand that this allows them to
not have any cost model for hoisting too far but code-size wise there will be missed opportunities.
I agree the design of llvm's gvn-hoist is not very clean mostly because it went multiple iterations, your ideas helped very much to write an optimistic algorithm and incorporate Memory SSA.
See https://reviews.llvm.org/D8688#a1aa52c6
computeBarriers, for a way to compute the barriers once and be able to constant time check whether they are in the way.
(since you have dfs numbers for the instructions)
Thanks, I'll study them.
FWIW, as i mentioned offline, these are trivially fixable without a complex algorithm.
They have simply chosen not to because it has not been worth it, AFAIK.
I agree the design of llvm's gvn-hoist is not very clean mostly because it went multiple iterations,
Gotta be honest:
At some point, you have to take the code that was a prototype, learn from it, and then write a clean version that is sane.
NewGVN went through a ton of iterations and ugly ass code, as chandler can tell you. At some point, we just sat down, said "okay, this is probably a *design* that works, now how do we make it look at least mildly sane".
your ideas helped very much to write an optimistic algorithm and incorporate Memory SSA.
isGuaranteedToTransferExecutionToSuccessor checks for three classes of instructions:
- TerminatorInst
- Memory operations
- Calls
For TerminatorInst, GVNHoist is using isGuaranteedToTransferExecutionToSuccessor
Memory operations are handled in safeToHoistLdSt which uses MemorySSA which returns/should return the MemoryAccess which might alter a memory operation (GVNHoist.cpp:478)
Calls are also handled separately in GVNHoist with partial help from MemorySSA GVNHoist.cpp:385, 492, 494
Honestly, i think a large amount of the commentary on this review would have been avoided with clear, concise, and centralized code that mapped existing and well known idioms for doing these things in llvm into the way you achieve the same result.
The reason to handle them separately is because:
- We would need to call isGuaranteedToTransferExecutionToSuccessor for all instructions in path which won't be efficient
- MemorySSA does most parts of isGuaranteedToTransferExecutionToSuccessor in more efficient way by iterating over instructions which might affect memory.
I can do that in a separate patch. This patch related to fixing a correctness bug (at -Os, -Oz). https://bugs.llvm.org//show_bug.cgi?id=31729
NewGVN went through a ton of iterations and ugly ass code, as chandler can tell you. At some point, we just sat down, said "okay, this is probably a *design* that works, now how do we make it look at least mildly sane".
your ideas helped very much to write an optimistic algorithm and incorporate Memory SSA.
While the if (OptForMinSize && isSafeToSpeculativelyExecute(I)) fix doesn't look great, and the discussion suggests there might be more fundamental problems with GVNHoist, at least this seems like a good stop-gap fix for 4.0.
If I understand correctly, the impact will be some compile-time reduction at -Oz, less hoisting, and more correctness.
Honestly, I'm not sure I agree. I think the safer thing to do would be to rip out the OptForMinSize handling from the 4.0 release.
Okay I'll remove -Os handling for aggressive hoisting for now. Thanks for the feedback.
Addressing David's comment to remove hoisting of scalars without comprehensive checks at -Os/-Oz.
I hadn't seen that check before, but I agree with David that it looks scary.
What is the check doing anyway? It sounds like we don't think it's safe to hoist this kind of instruction; why is it safe to hoist past it, and what has OptForMinSize got to do with it?
I'm testing another patch which will remove OptForMinSize completely. I'll improve that in the next release cycle and hope it gets committed.
Please feel free to commit this patch if there is hurry as I do not have commit access from my office machine.
Actually, you changed from
if (Call->mayHaveSideEffects()) {
if (!OptForMinSize)
break;
// We may continue hoisting across calls which write to memory.
if (Call->mayThrow())
break;
}to
if (Call->mayHaveSideEffects()) {
// We may continue hoisting across calls which write to memory.
if (Call->mayThrow())
break;
}which means rather than disabling this also for -Oz, you enabled it for all levels.
I'll fix this when committing.
I also note that there are no tests covering this.