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

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>

On Mon, Jan 23, 2017 at 1:09 AM Chandler Carruth via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> 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.
>
FYI: the initial patch doing exactly this and cleaning up the new PM as a
consequence is here: https://reviews.llvm.org/D29006

Just figured I'd give folks a concrete idea of the impact and scope of this.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170123/13fd9f95/attachment.html>

On 01/23/2017 03:08 AM, Chandler Carruth wrote:
> 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 
> <mailto: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.
I agree; having an analysis that all clients need to promise not to 
invalidate in certain ways is troublesome.

  -Hal
> 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.111
>
>
> 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
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

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

On the code review thread, Sanjoy mentioned:

(I hope the formatting isn't too broken)
>>! In D29006#653587, @sanjoy wrote:
> Hi Chandler,
>
> I'm not sure this is a good idea.
>
> If this is the *only* path forward then I'll be okay going ahead with
> it, but I think `AssertingVH` (not unlike most other similar things)
> is useful and provides a superset of functionality provided by
> sanitizers.
Note that the biggest advantage IMO is the ability to error immediately on
the deletion as that points to the cause of the bug. Anything we build here
will instead point to the point of use which is a bit unfortunate. ASan's
heap-use-after-free is actually better at this because it stores the stack
trace for the deletion and shows it. I don't really want to try to rebuild
that functionality.
>
>> For example, a debug-build-only
>> WeakVH and an explicit assert that it hasn't gone null when it is
*used*
>> so that it can still *exist* even when the value goes away.
>
> But we don't *have* such a thing today, and for that reason this
> change is a strict decrease in debug-ability.  If you wanted to add
> something like that, and replace existing `AssertingVH` uses with it
> then I may feel better about this; however `AssertingVH` is stronger
> than what you suggest since `AssertingVH` catches cases where we've
> keyed a hash table off `AssertingVH` s.  To be on part with that
> functionality, we'd also need to write data structures like `DenseMap`
> that can be "poisoned" by a `CallbackVH` key.
As I mention above, I actually think AssertingVH is stronger than ASan
because it triggers the error on deletion.

ASan will use a quarantine to work quite hard to avoid accidental re-use of
an entry for a newly allocated pointer. So most bugs with hash tables I
would still expect something like ASan to uncover. The only things it won't
find are when getting a fresh address masks the bug *and* you don't ever
re-use the stale key in any way. That is a hole in the ASan based approach,
although historically I have not had this be a frequent failure mode. But
that's just me, and I've honestly not worked on SCEV or LVI enough to
have
any intuition about those passes.

Anyways, I have built the replacement. It's somewhat awful IMO, but it will
at least cover the case above. It will be somewhat harder to debug than an
ASan failure as it won't give a backtrace for the deletion, but you can set
a breakpoint to get that in a debugger.

Patch adding a "poisoning" VH: https://reviews.llvm.org/D29061
Updated patch using it: https://reviews.llvm.org/D29006

Thoughts?
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170124/c8993465/attachment.html>

On Mon, Jan 23, 2017 at 1:08 AM, Chandler Carruth <chandlerc at gmail.com>
wrote:
> 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.
>
Yeah, this is the crux of the problem and clearly incompatible with caching
that is updated at the boundaries of transformation pass runs. The
operations you're allowed to do or not on the IR should not depend on what
analyses happen to be cached or not. For an analysis to hold an AssertingVH
is basically saying "you cannot delete this part of the IR as long as
I'm
cached" which is not something an analysis should be allowed to do IMO.

In principle, one alternative is to trigger the invalidation of the cached
analysis result right before we delete the thing it is holding the
AssertingVH on. But then in what sense in the AssertingVH actually
"asserting"? At that point it is just a CallbackVH that triggers
invalidation.

> 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.
>
SGTM.

-- Sean Silva

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

Cool, moving forward with this as Sanjoy clarified on the patches that he's
also happy with this result and everyone else seems happy as well.

Thanks!
-Chandler

On Mon, Jan 23, 2017 at 10:07 PM Sean Silva <chisophugis at gmail.com>
wrote:
> On Mon, Jan 23, 2017 at 1:08 AM, Chandler Carruth <chandlerc at
gmail.com>
> wrote:
>
> 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.
>
>
> Yeah, this is the crux of the problem and clearly incompatible with
> caching that is updated at the boundaries of transformation pass runs. The
> operations you're allowed to do or not on the IR should not depend on
what
> analyses happen to be cached or not. For an analysis to hold an AssertingVH
> is basically saying "you cannot delete this part of the IR as long as
I'm
> cached" which is not something an analysis should be allowed to do
IMO.
>
> In principle, one alternative is to trigger the invalidation of the cached
> analysis result right before we delete the thing it is holding the
> AssertingVH on. But then in what sense in the AssertingVH actually
> "asserting"? At that point it is just a CallbackVH that triggers
> invalidation.
>
>
> 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.
>
>
> SGTM.
>
> -- Sean Silva
>
>
>
> -Chandler
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170124/d1eff2e9/attachment.html>

> On Jan 23, 2017, at 10:07 PM, Sean Silva <chisophugis at gmail.com>
wrote:
> 
> 
> 
> On Mon, Jan 23, 2017 at 1:08 AM, Chandler Carruth <chandlerc at
gmail.com <mailto:chandlerc at gmail.com>> wrote:
> 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
<mailto: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.
> 
> Yeah, this is the crux of the problem and clearly incompatible with caching
that is updated at the boundaries of transformation pass runs. The operations
you're allowed to do or not on the IR should not depend on what analyses
happen to be cached or not. For an analysis to hold an AssertingVH is basically
saying "you cannot delete this part of the IR as long as I'm
cached" which is not something an analysis should be allowed to do IMO.
Another view of it is that there should be another handle that triggers the
invalidation of the analysis when this IR is changed: i.e. keeping the analysis
cached while it holds a reference to the IR can be seen as the problem.

— 
Mehdi


> 
> In principle, one alternative is to trigger the invalidation of the cached
analysis result right before we delete the thing it is holding the AssertingVH
on. But then in what sense in the AssertingVH actually "asserting"? At
that point it is just a CallbackVH that triggers invalidation.
>  
> 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.
> 
> SGTM.
> 
> -- Sean Silva
>  
> 
> -Chandler
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170124/4f68f35f/attachment-0001.html>