llvm dev - Jul 2016 - Should analyses be able to hold AssertingVH to IR? (related to PR28400)

While building test-suite with the new PM, I ran into problems with
AssertingVH being triggered which is obvious in retrospect:
https://llvm.org/bugs/show_bug.cgi?id=28400

Both cases I ran into revolve around LVI which holds AssertingVH.
Essentially, what happens is this:

1. LVI holds an AssertingVH pointing at a BasicBlock
2. Some other pass ends up deleting that BB (e.g. SimplifyCFG)
3. BOOM

Notice that this ends up happening even though SimplifyCFG ultimately
invalidates LVI. But that only happens after the AssertingVH has been
triggered.

We would avoid this issue in principle by just switching those AssertingVH
to observing pointers, but then we would have dangling pointers. I'm pretty
sure that any analysis that keeps pointers to IR is in fact ending up with
dangling pointers like this.

I've noticed that AssumptionCache using CallbackVH that allow it to update
its data structures correctly in this case.

Just using regular pointers will end up with dangling pointers in this
scenario. This isn't a problem in practice since the analysis will
hopefully be invalidated and stop holding the dangling pointers, but it
just seems weird. Thankfully, ASan can generally catch problems if we do
try to access through any of these dangling pointers.

Thoughts? For the moment I have put in a workaround (r274457) that makes
jump-threading invalidate LVI.

-- Sean Silva
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160705/ceeb69a2/attachment.html>

Hi Sean,

Sean Silva wrote:
 > While building test-suite with the new PM, I ran into problems with
 > AssertingVH being triggered which is obvious in retrospect:
 > https://llvm.org/bugs/show_bug.cgi?id=28400
 >
 > Both cases I ran into revolve around LVI which holds AssertingVH.
 > Essentially, what happens is this:
 >
 > 1. LVI holds an AssertingVH pointing at a BasicBlock
 > 2. Some other pass ends up deleting that BB (e.g. SimplifyCFG)
 > 3. BOOM
 >
 > Notice that this ends up happening even though SimplifyCFG ultimately
 > invalidates LVI. But that only happens after the AssertingVH has been
 > triggered.
 >
 > We would avoid this issue in principle by just switching those
 > AssertingVH to observing pointers, but then we would have dangling
 > pointers. I'm pretty sure that any analysis that keeps pointers to IR
is
 > in fact ending up with dangling pointers like this.
 >
 > I've noticed that AssumptionCache using CallbackVH that allow it to
 > update its data structures correctly in this case.
 >
 > Just using regular pointers will end up with dangling pointers in this
 > scenario. This isn't a problem in practice since the analysis will
 > hopefully be invalidated and stop holding the dangling pointers, but it
 > just seems weird. Thankfully, ASan can generally catch problems if we do
 > try to access through any of these dangling pointers.

But asan won't catch problems (insofar I understand how it works) if
the free'ed BasicBlock is used as a key in a DenseMap or something --
if another BasicBlock gets allocated to the same location we'll end up
returning bad cached results.

I think the Right Solution(TM) here is to create a new wrapper around
(Small)DenseMap that in debug mode uses a CallbackVH in a way that:

  - The map is "poisoned" if a key is deleted.
  - A poisoned map can only be cleared; inserting, removing or looking
    up elements in a poisoned map fails a assertions.

If needed, we can allow erasing deleted keys from poisoned maps, but
then we won't catch bugs like:

   M[k] = v;
   delete k;
   k1 = new Key();  // allocated to the same location as k1
   M.erase(k1);  // "successful" deletion.

However, this quite a bit of work, and I'm not sure if the payoff will
be worth it.

-- Sanjoy

 > Thoughts? For the moment I have put in a workaround (r274457) that makes
 > jump-threading invalidate LVI.
 >
 > -- Sean Silva

On Mon, Jul 11, 2016 at 7:51 PM, Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> Hi Sean,
>
> Sean Silva wrote:
> > While building test-suite with the new PM, I ran into problems with
> > AssertingVH being triggered which is obvious in retrospect:
> > https://llvm.org/bugs/show_bug.cgi?id=28400
> >
> > Both cases I ran into revolve around LVI which holds AssertingVH.
> > Essentially, what happens is this:
> >
> > 1. LVI holds an AssertingVH pointing at a BasicBlock
> > 2. Some other pass ends up deleting that BB (e.g. SimplifyCFG)
> > 3. BOOM
> >
> > Notice that this ends up happening even though SimplifyCFG ultimately
> > invalidates LVI. But that only happens after the AssertingVH has been
> > triggered.
> >
> > We would avoid this issue in principle by just switching those
> > AssertingVH to observing pointers, but then we would have dangling
> > pointers. I'm pretty sure that any analysis that keeps pointers to
IR is
> > in fact ending up with dangling pointers like this.
> >
> > I've noticed that AssumptionCache using CallbackVH that allow it
to
> > update its data structures correctly in this case.
> >
> > Just using regular pointers will end up with dangling pointers in this
> > scenario. This isn't a problem in practice since the analysis will
> > hopefully be invalidated and stop holding the dangling pointers, but
it
> > just seems weird. Thankfully, ASan can generally catch problems if we
do
> > try to access through any of these dangling pointers.
>
> But asan won't catch problems (insofar I understand how it works) if
> the free'ed BasicBlock is used as a key in a DenseMap or something --
> if another BasicBlock gets allocated to the same location we'll end up
> returning bad cached results.
>
ASan's allocator is specifically hardened against reusing memory, which
mitigates this, but I'm not sure by how much (but I think by a significant
amount).


>
> I think the Right Solution(TM) here is to create a new wrapper around
> (Small)DenseMap that in debug mode uses a CallbackVH in a way that:
>
>  - The map is "poisoned" if a key is deleted.
>  - A poisoned map can only be cleared; inserting, removing or looking
>    up elements in a poisoned map fails a assertions.
>
> If needed, we can allow erasing deleted keys from poisoned maps, but
> then we won't catch bugs like:
>
>   M[k] = v;
>   delete k;
>   k1 = new Key();  // allocated to the same location as k1
>   M.erase(k1);  // "successful" deletion.
>
> However, this quite a bit of work, and I'm not sure if the payoff will
> be worth it.

Hmm.. interesting idea but yeah that seems like a lot of work. From my
basic testing, it seems like LVI is the only analysis that uses this
pattern so I'm especially not sure it is worth it for a single analysis
(unless we want to change more analyses to use this pattern).

There's a relatively simple workaround for now which is manually
invalidating LVI at the end of passes that use it (JumpThreading and
CorrelatedValuePropagation).

-- Sean Silva

>
>
> -- Sanjoy
>
>
> > Thoughts? For the moment I have put in a workaround (r274457) that
makes
> > jump-threading invalidate LVI.
> >
> > -- Sean Silva
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160711/673ccac6/attachment.html>

On Tue, Jul 5, 2016 at 6:56 PM, Sean Silva <chisophugis at gmail.com>
wrote:
> While building test-suite with the new PM, I ran into problems with
> AssertingVH being triggered which is obvious in retrospect:
> https://llvm.org/bugs/show_bug.cgi?id=28400
>
> Both cases I ran into revolve around LVI which holds AssertingVH.
> Essentially, what happens is this:
>
> 1. LVI holds an AssertingVH pointing at a BasicBlock
> 2. Some other pass ends up deleting that BB (e.g. SimplifyCFG)
> 3. BOOM
>
> Notice that this ends up happening even though SimplifyCFG ultimately
> invalidates LVI. But that only happens after the AssertingVH has been
> triggered.
>
> We would avoid this issue in principle by just switching those AssertingVH
> to observing pointers, but then we would have dangling pointers. I'm
pretty
> sure that any analysis that keeps pointers to IR is in fact ending up with
> dangling pointers like this.
>
> I've noticed that AssumptionCache using CallbackVH that allow it to
update
> its data structures correctly in this case.
>
> Just using regular pointers will end up with dangling pointers in this
> scenario. This isn't a problem in practice since the analysis will
> hopefully be invalidated and stop holding the dangling pointers, but it
> just seems weird. Thankfully, ASan can generally catch problems if we do
> try to access through any of these dangling pointers.
>
> Thoughts? For the moment I have put in a workaround (r274457) that makes
> jump-threading invalidate LVI.
>
Is everybody happy with this workaround? Although I mentioned it a couple
times in this thread nobody seems to have explicitly commented on it.

This issue does manifest in almost any non-trivial pipeline containing
affected analyses (analyses that use AssertingVH to reference pieces of IR;
in particular, LazyValueInfo, ScalarEvolution, and CallGraph) and this
workaround seems simple enough for the moment.

One caveat I ran into is that if you ever manually
`require<scalar-evolution>` (as you would before entering a loop pass
manager with a loop pass that needs ScalarEvolution), you need to remember
to `invalidate<scalar-evolution>` after running the loop passes to make
sure it gets invalidated.

-- Sean Silva

>
> -- Sean Silva
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160808/d33423b8/attachment-0001.html>

This thread kinda died. I'd like to revive it.

The new PM stuff is making excellent progress, and this is actually one of
the last things to clean up.

On Mon, Aug 8, 2016 at 1:10 AM Sean Silva <chisophugis at gmail.com>
wrote:
> Thoughts? For the moment I have put in a workaround (r274457) that makes
> jump-threading invalidate LVI.
>
>
> Is everybody happy with this workaround?
>
I wasn't too happy with it, but I had no better suggestion.

As the infrastructure matured, what I think is a substantially less
horrible workaround is available in the form of what I implemented in
r292773. Instead of just working around this for each analysis, this works
around it in GlobalDCE for *any* function analysis stashing an AssertingVH.
The down side is that it only defends against *function* removal and
*function* analyses. =[

This may be a tiny bit better in some senses, but in others its worse, and
frankly I think it is a pretty gross hack even in the best of cases. But
let's take a look at some of the cases you identified:

#1: CallGraph has an asserting VH on functions. But my workaround doesn't
help at all, much to my surprise afterward! Why? Well of course because
CallGraph is a *module analysis*. We can't just go invalidating every
module analysis every time we remove a function... :: sigh ::

#2: SCEV and LVI have *basic block* asserting VHs. For some reason, all the
test cases I have stem from deleting an entire function, but there is no
real reason that will be the case. It seems entirely plausible to nuke a
basic block out from under one of these.

So no, I think we need a better answer here.


After thinking about this a lot, and trying and failing to implement less
awful workarounds, I think AssertingVHes embedded in analysis results in
fundamentally incompatible with caching of results.

The cache gets invalidated automatically but not the instant the IR gets
mutated. The assert happens too soon, and things blow up. I don't think we
want to force cache invalidation logic in every pass that deletes a Value.
=[

So I think we should move away from AssertingVH in analysis results. If you
need a more powerful debugging tool than ASan (or analogous) provides, we
can build a DebugOnlyWeakVH or some such that becomes null immediately in
debug builds. Or that has a asserting-only-if-used behavior rather than the
eager assert we have today. But I'm inclined to build that tool when folks
are first debugging something and tools like ASan are insufficient rather
than eagerly.


Any objections to this? I'd really like to nuke the 3 cases Sean identified
in the tree (CallGraph, LVI, SCEV) and stop hacking around them.

-Chandler
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170123/0e190ef7/attachment.html>