Sanjoy Das
2015-Feb-24 05:52 UTC
[LLVMdev] Jump Theading/GVN bug - moving discussion to llvm-dev
> Programmers don't usually write code like this directly, but it is common > for it to happen as a result of the expansion of macros or inline functions. > You would not want to require that a compiler front end *not* produce this.I meant to say that whatever mechanism we use to track dead blocks that may exhibit edge-cases of SSA def-use behavior does *not* need to be clever enough to deal with this example, since the verifier rejects this snippet (def of %m does not dominate its use). If all we care about are blocks that have to follow def-dominates-use in the intuitive sense then a super simple succ_begin()/succ_end() based DFS is sufficient. What I don't know is whether such a thing will be fast enough. In any case, I don't have enough experience with LLVM to have a strong / defensible opinion on this, and I'll defer to the decision taken by people who do. -- Sanjoy
Daniel Berlin
2015-Feb-24 06:31 UTC
[LLVMdev] Jump Theading/GVN bug - moving discussion to llvm-dev
Yes, in fact, for each pass, at worst, even if the pass had no idea how to clean up unreachable code as it went (and again, most do, because most compiler algorithms are built with the idea that they need to clean up after themselves), your algorithm is what the entirety of "find unreachable code" looks like for gcc. As for compile time, *we already do it* (see simplifycfg) :) We just don't try to prevent things like jump threading from messing it up. and again, the number of places that will mess it up are very small. Most algorithms were built to track what dead code they were adding (whether LLVM implemented that part of the algorithm or not). As an example, look at GVN.cpp's addDeadBlock, SCCP's code to avoid messing up the CFG (IPSCCP knows how to delete dead blocks, SCCP preserves CFG so it just doesn't mess with the terminators, etc), etc The hardest pass to make stop generating unreachable code tends to be jump threading, but this is more because "nobody has written it down in a book" than "it is hard to do" :) On Mon, Feb 23, 2015 at 9:52 PM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote:> > Programmers don't usually write code like this directly, but it is common > > for it to happen as a result of the expansion of macros or inline > functions. > > You would not want to require that a compiler front end *not* produce > this. > > I meant to say that whatever mechanism we use to track dead blocks > that may exhibit edge-cases of SSA def-use behavior does *not* need to > be clever enough to deal with this example, since the verifier rejects > this snippet (def of %m does not dominate its use). If all we care > about are blocks that have to follow def-dominates-use in the > intuitive sense then a super simple succ_begin()/succ_end() based DFS > is sufficient. What I don't know is whether such a thing will be fast > enough. > > In any case, I don't have enough experience with LLVM to have a strong > / defensible opinion on this, and I'll defer to the decision taken by > people who do. > > -- Sanjoy > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150223/c1983e92/attachment.html>
Sanjoy Das
2015-Feb-24 06:51 UTC
[LLVMdev] Jump Theading/GVN bug - moving discussion to llvm-dev
Is it fair (and correct) to say that the main issue with unreachable code is this: if we allow unreachable code then the dom tree is no longer a tree, it can have components (disconnected from the root) that are cycles. So no pass that wants to just work with unreachable code can depend on the dom tree actually being a tree. Or are there more fundamental issues (I realize the dom tree not being a tree is rather fundamental itself)? -- Sanjoy