On 07/17/2014 01:51 PM, Chandler Carruth wrote:> > > 2. Would adding a canonicalization of if(c) { unreachable } to > llvm.invariant(c) would be worthwhile? > > > There was a long and painful attempt to implement invariants based on > the branch-to-unreachable pattern. It didn't work. I don't expect > these patterns to show up often organically and to go away too soon in > the optimizer to be useful. The whole point of 'llvm.invariant' > instead of the if construct is to distinguish between the case the > optimizer should try to remove (a branch to unreachable) and the case > the optimizer should try to preserve because of some specific utility. > We shouldn't lose this important distinction.On first thought, I disagree. I may not be understanding your point though. My understanding of the previous work was that it tried to use "branch-to-unreachable" as the canonical form. This is inherently problematic in an IR based on basic blocks since it split basic blocks into many smaller chunks. It might work out better if we used extended basic blocks, but we don't. I don't see any harm in canonicalizing to "llvm.invariant" from "if(c) unreachable". In either case, we remove the branch and can merge the basic blocks. In the former, we preserve more information for later passes. The only real downside is potentially keeping more Values alive and thus forcing the compiler to do more work. Can you spell out your objections more?> > > 2. We might want to have passes precompute the Value->(set of > Invariants) map, and update it as necessary instead of doing > transitive-user searches [a suggestion by Chandler]. > > > I think this is mostly just a small API tweak to make the code more > maintainable. I'm specifically *not* imagining this as a formal > analysis pass or anything of the sort.I would support this. I'm not seeing the downside to an analysis pass. Probably not worth implementing up front, but might be worthwhile down the road. Philip -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140717/c3f0ceef/attachment.html>
On Thu, Jul 17, 2014 at 5:38 PM, Philip Reames <listmail at philipreames.com> wrote:> On 07/17/2014 01:51 PM, Chandler Carruth wrote: > > > > 2. Would adding a canonicalization of if(c) { unreachable } to >> llvm.invariant(c) would be worthwhile? >> > > There was a long and painful attempt to implement invariants based on > the branch-to-unreachable pattern. It didn't work. I don't expect these > patterns to show up often organically and to go away too soon in the > optimizer to be useful. The whole point of 'llvm.invariant' instead of the > if construct is to distinguish between the case the optimizer should try to > remove (a branch to unreachable) and the case the optimizer should try to > preserve because of some specific utility. We shouldn't lose this important > distinction. > > On first thought, I disagree. I may not be understanding your point > though. > > My understanding of the previous work was that it tried to use > "branch-to-unreachable" as the canonical form. This is inherently > problematic in an IR based on basic blocks since it split basic blocks into > many smaller chunks. It might work out better if we used extended basic > blocks, but we don't. > > I don't see any harm in canonicalizing to "llvm.invariant" from "if(c) > unreachable". In either case, we remove the branch and can merge the basic > blocks. In the former, we preserve more information for later passes. The > only real downside is potentially keeping more Values alive and thus > forcing the compiler to do more work. > > Can you spell out your objections more?Adding an invariant has a cost. Just because we nuked a branch doesn't mean that the condition feeding the branch is definitely a high-value invariant to preserve in the IR. I wouldn't mind an experiment to see if this ended up being profitable, but I'm dubious about it's profitability so far, and would want to see data to back up this change as I worry about significantly increasing the density of invariants (and thus their compile time cost and cost on hasOneUse failures) without any real benefit. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140717/a783a445/attachment.html>
On 07/17/2014 02:46 PM, Chandler Carruth wrote:> > On Thu, Jul 17, 2014 at 5:38 PM, Philip Reames > <listmail at philipreames.com <mailto:listmail at philipreames.com>> wrote: > > On 07/17/2014 01:51 PM, Chandler Carruth wrote: >> >> >> 2. Would adding a canonicalization of if(c) { unreachable } >> to llvm.invariant(c) would be worthwhile? >> >> >> There was a long and painful attempt to implement invariants >> based on the branch-to-unreachable pattern. It didn't work. I >> don't expect these patterns to show up often organically and to >> go away too soon in the optimizer to be useful. The whole point >> of 'llvm.invariant' instead of the if construct is to distinguish >> between the case the optimizer should try to remove (a branch to >> unreachable) and the case the optimizer should try to preserve >> because of some specific utility. We shouldn't lose this >> important distinction. > On first thought, I disagree. I may not be understanding your > point though. > > My understanding of the previous work was that it tried to use > "branch-to-unreachable" as the canonical form. This is inherently > problematic in an IR based on basic blocks since it split basic > blocks into many smaller chunks. It might work out better if we > used extended basic blocks, but we don't. > > I don't see any harm in canonicalizing to "llvm.invariant" from > "if(c) unreachable". In either case, we remove the branch and can > merge the basic blocks. In the former, we preserve more > information for later passes. The only real downside is > potentially keeping more Values alive and thus forcing the > compiler to do more work. > > Can you spell out your objections more? > > > Adding an invariant has a cost. Just because we nuked a branch doesn't > mean that the condition feeding the branch is definitely a high-value > invariant to preserve in the IR. > > I wouldn't mind an experiment to see if this ended up being > profitable, but I'm dubious about it's profitability so far, and would > want to see data to back up this change as I worry about significantly > increasing the density of invariants (and thus their compile time cost > and cost on hasOneUse failures) without any real benefit.Given your explanation in the other response, your position makes a lot more sense. I agree it makes sense to run the experiment, but for now, I'm happy accepting your position as a reasonable default. I find myself wondering if we might want to remove invariants somewhat aggressively. Thinking about exactly when this would be profitably will require some serious thought through. It doesn't appear to have an obvious "right" answer. Philip -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140717/fb30a671/attachment.html>