New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[LazyValueInfo] Assertion `isa<Argument>(Val) && "Unknown live-in to the entry block"' failed. #27092
Comments
assigned to @preames |
No file has been attached. |
This is probably fall out from my recent LVI changes. If you can get me a reproducer, I'll investigate. |
[Bugpoint reduced sample file derived from test-suitehttps://user-images.githubusercontent.com/2278807/143753089-a6810b3e-efd7-42ef-b69c-0aba831ee7eb.gz) |
This really looks like invalid IR. Here's the key piece: The second phi's inputs are the first phi in the same block. This is leading us to do queries on %x.addr.0.ph.merge outside of it's defining block, but the root issue appears to be invalid IR. Looking at the verifier, I noticed that we're whitelisting instructions in the same basic block for dominance queries. This is likely fine for all non-phi instructions, but appears to be incorrect for phis. Michael, can you tweak the Verifier with the following diff and then try re-reducing? I suspect there is a real problem here, but the example bugpoint produced is invalid.
|
Er, I don't see why a phi cannot have an input from another phi in the same BB. |
David, if that is legal, I suspect we need to audit large parts of the optimizer which assume otherwise. To be clear, the basic block is not part of a cycle in the CFG. The lang ref seems pretty clear about this: The PHI input is not available on the edge specified. It's only defined in the given basic block and there's no cycles in the CFG by which it can dominate the incoming edge. What am I missing? |
Yeah, I don't think define void @f() { next: should pass the verifier (which it does today). |
I've certainly forced myself to consider such cases when writing code which deals with a PHI's uses. FWIW, Transforms/LoopVectorize/phi-hang.ll in the tests directory appears to be checking for this exact case. I don't think it would be crazy to say that the langref might not be correct here. Perhaps I am wrong. It would be good to take this to the list. |
Some thoughts on this: The debate seems to be between a "strict interpretation" of PHIs that requires a source to be dominated by the corresponding incoming edge, and a "loose interpretation" that allows a source to be a preceding PHI in the same block. Separate but related to the question of what the verifier allows is what are the semantics of PHIs. In particular, does the evaluation of a PHI source occur in the context of the predecessor edge/block, or does it occur in the context of the block holding the PHI? declare i32 @f() define void @foo(i1 %b1) {
So the "loose interpretation" would force us to pick which semantics we infer for cases like the third (use of a previous phi in the same block, but tied to an edge that is a back-edge), and it will disagree with either the first type (use of a value dominating the pred but not the PHI block) or the second type (use of a previous PHI in the same block on a non-back edge). I'd rather not have to pick (by choosing the "strict interpretation", outlawing the second type, and having the first and third types consistent). Now, I don't know if this next part is controversial, but I think the "evaluated in the context of the predecessor" semantics are the best choice for the same-block back-edge cases. For one, that seems to be how lowering currently interprets PHIs; if I compile and run this program:
It prints For another thing, adopting the "evaluate in the context of the phi block" semantics would complicate reasonable transformations. Consider an example like this: Third, it's my impression that "the literature" universally takes this view; two good references are
If those are compelling reasons to prefer the "evaluate in the context of the back-edge" semantics (as I think they are), then using the "loose interpretation" and allowing PHI sources to be preceding PHIs in the same block, unless I'm missing something, means that if you see |
I regenerated the file in question and can confirm that it contains a phi using another phi in the same BB. The verifier with the suggestion change rejects it. I therefore think it does not make sense to bugpoint-reduce it again. Please notify me if you still think it is useful. It is the output of my own modification, hence not a direct bug in LLVM. However, I'd expect that the verifier reports it if it is not well-formed. Thanks to Joseph Tremoulet for his elaboration. I also think it makes more sense to reject such IR instead of making all passes handle it. It doesn't add any expressiveness because next: has the same meaning as, and can easily be converted to: next: (assuming that 'next' is not in a loop) Michael |
Of course a phi can use another phi in the same block that is a self-loop. We cannot also allow phi def-use chains within a block. That's an obvious contradiction. Since those semantics would not be well defined, I can't see how a pass could handle this case and be correct in general. A block's phis are unordered, and passes need to be able to assume that. The verifier should fail on this IR. It's shocking that it doesn't. |
"Fixed" as the verifier now rejects such IR since http://reviews.llvm.org/D18443 (r264528) During the review Sanjoy mentioned that InstsInThisBlock is just a performance optimization to quickly accept instructions that were just seen in the BasicBlock. This means it should behave the same as if only DT.dominates(Op, U) decides whether it the domination is correct, which rejects such IR. |
Extended Description
The attached file crashes in the correlated value propagation pass. LLVM trunk r261633.
$ ~/build/llvm/debug/bin/opt z08_bugpoint.ll -verify -correlated-propagation -analyze
Printing analysis 'Module Verifier' for function 'Manifest':
Pass::print not implemented for pass: 'Module Verifier'!
opt: /home/meinersbur/src/llvm/lib/Analysis/LazyValueInfo.cpp:766: bool {anonymous}::LazyValueInfoCache::solveBlockValueNonLocal({anonymous}::LVILatticeVal&, llvm::Value*, llvm::BasicBlock*): Assertion `isa(Val) && "Unknown live-in to the entry block"' failed.
0 opt 0x0000000001dd2f80 llvm::sys::PrintStackTrace(llvm::raw_ostream&) + 59
1 opt 0x0000000001dd32d8
2 opt 0x0000000001dd180f llvm::sys::RunSignalHandlers() + 153
3 opt 0x0000000001dd299c
4 libpthread.so.0 0x00007fcc16cf7d10
5 libc.so.6 0x00007fcc15e97267 gsignal + 55
6 libc.so.6 0x00007fcc15e98eca abort + 362
7 libc.so.6 0x00007fcc15e9003d
8 libc.so.6 0x00007fcc15e900f2
9 opt 0x000000000127373f
10 opt 0x0000000001272d67
11 opt 0x000000000127274c
12 opt 0x0000000001275efc
13 opt 0x00000000012768f8 llvm::LazyValueInfo::getConstantOnEdge(llvm::Value*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::Instruction*) + 188
14 opt 0x0000000001b81a68
15 opt 0x0000000001b827d4
16 opt 0x0000000001848e82 llvm::FPPassManager::runOnFunction(llvm::Function&) + 330
17 opt 0x000000000184901b llvm::FPPassManager::runOnModule(llvm::Module&) + 133
18 opt 0x0000000001849396
19 opt 0x0000000001849aab llvm::legacy::PassManagerImpl::run(llvm::Module&) + 271
20 opt 0x0000000001849cb7 llvm::legacy::PassManager::run(llvm::Module&) + 39
21 opt 0x0000000000f01314 main + 7148
22 libc.so.6 0x00007fcc15e82a40 __libc_start_main + 240
23 opt 0x0000000000edbd79 _start + 41
Stack dump:
0. Program arguments: /home/meinersbur/build/llvm/debug/bin/opt z08_bugpoint.ll -verify -correlated-propagation -analyze
Aborted (core dumped)
The text was updated successfully, but these errors were encountered: