llvm dev - Feb 2015 - [LLVMdev] Jump Theading/GVN bug - moving discussion to llvm-dev

> Handling unreachable code is annoying. I agree. However, its important to
> characterize how annoying. Most code is not unreachable, and we're
> (obviously) fine just bailing on such crazy code paths. So in practice the
> common cost is keeping a local set to detect cycles in the graph where we
> aren't expecting them. We are essentially always traversing a linked
list
> representing this graph. Because these linked list nodes don't have any
> particular reason to have high locality, we have a cache-hostile traversal
> where we have to do primarily local and cache friendly book-keeping at each
> step to catch duplication. I suspect that this has a very small (but
> non-zero) impact on compile time.
Why not have an analysis pass that does a DFS starting from the entry
block?  Is that likely to be very costly?  Having an analysis pass is
attractive because that allows some transformation passes to put in
some extra work to preserve it if they so desire.

The analysis pass does not have to be clever at all, since the
verifier (rightly, I think) considers a block reachable even if it is
predicated on a literal false -- the following IR does not verify:

define void @f() {
 entry:
  br i1 false, label %t, label %f

 t:
  ret void

 f:
  %m = add i32 %m, 1
  ret void
}

-- Sanjoy

>   br i1 false, label %t, label %f
Typo -- should be "br i1 true ..."

On Tue, Feb 24, 2015 at 5:56 PM, Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> > Handling unreachable code is annoying. I agree. However, its important
to
> > characterize how annoying. Most code is not unreachable, and we're
> > (obviously) fine just bailing on such crazy code paths. So in practice
> the
> > common cost is keeping a local set to detect cycles in the graph where
we
> > aren't expecting them. We are essentially always traversing a
linked list
> > representing this graph. Because these linked list nodes don't
have any
> > particular reason to have high locality, we have a cache-hostile
> traversal
> > where we have to do primarily local and cache friendly book-keeping at
> each
> > step to catch duplication. I suspect that this has a very small (but
> > non-zero) impact on compile time.
>
> Why not have an analysis pass that does a DFS starting from the entry
> block?  Is that likely to be very costly?  Having an analysis pass is
> attractive because that allows some transformation passes to put in
> some extra work to preserve it if they so desire.
>
> The analysis pass does not have to be clever at all, since the
> verifier (rightly, I think) considers a block reachable even if it is
> predicated on a literal false -- the following IR does not verify:
>
> define void @f() {
>  entry:
>   br i1 false, label %t, label %f
>
>  t:
>   ret void
>
>  f:
>   %m = add i32 %m, 1
>   ret void
> }

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150224/a298314d/attachment.html>

> 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