llvm dev - Jan 2019 - Coupling between CaptureTracking and its users

Working on a downstream optimization which uses CaptureTracking (CT) I came
across a coupling problem. It looks like optimizations and analyses which use CT
often need to be in sync with CT implementation.

Analyzing the uses of the given pointer CT handles three kinds of uses:
 * Simple non-capturing use. When one is encountered, CT just moves on.
 * Non-capturing, but produces another value, which needs to be tracked.
   Examples: bitcasts, geps, phis, selects, etc. I’ll call this kind of uses
   "aliases", for the lack of better word.
 * Capturing.

The "aliases" are tricky. CT users often need to know about these. For
example,
rL331587<https://reviews.llvm.org/rL331587> taught CT the
"alias" semantic of launder.invariant.group calls.
Because BasicAA was not aware of this change, it lead to incorrect AA results.
"BasicAA still considered every call instruction as a possible escape
source and
hence concluded that the result of a launder_invariant_group call cannot alias
any local non-escaping value."
The first attempt to fix it fixed BasicAA
(rL332466<https://reviews.llvm.org/rL332466>), but apparently there were
similar issues in other parts. These were fixed by
rL333070<https://reviews.llvm.org/rL333070>.

Another example is our downstream optimization which does some sort of scalar
replacement of non-escaping allocations. It rewrites uses of the allocation and
needs to know about "aliases" as their uses also need to be rewritten.
Currently
it knows about all the "aliases" supported by CT, but it's not
resilient to
further changes in CT.

Proposal

Currently CaptureTracker is notified about capturing uses through
CaptureTracker::captured. I propose to notify the tracker about all the uses
explicitly specifying the kind (NoCapture, Alias, Capture). This way the tracker
can only accept Alias uses it knows how to handle. If something unexpected comes
up the tracker can give up the analysis.

The default tracker can ignore Alias uses under the assumption that upstream
users of CT maintain tight coupling with the analysis, like it is today.
Refactoring of upstream users of CT is out of scope for this proposal. But in
future they can be decoupled from CT implementation by explicitly checking the
Alias uses.

Thoughts?

Artur
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190104/d74aabe0/attachment.html>

On 1/4/19 5:24 PM, Artur Pilipenko via llvm-dev wrote:
Working on a downstream optimization which uses CaptureTracking (CT) I came
across a coupling problem. It looks like optimizations and analyses which use CT
often need to be in sync with CT implementation.

Analyzing the uses of the given pointer CT handles three kinds of uses:
 * Simple non-capturing use. When one is encountered, CT just moves on.
 * Non-capturing, but produces another value, which needs to be tracked.
   Examples: bitcasts, geps, phis, selects, etc. I’ll call this kind of uses
   "aliases", for the lack of better word.
 * Capturing.

The "aliases" are tricky. CT users often need to know about these. For
example,
rL331587<https://reviews.llvm.org/rL331587> taught CT the
"alias" semantic of launder.invariant.group calls.
Because BasicAA was not aware of this change, it lead to incorrect AA results.
"BasicAA still considered every call instruction as a possible escape
source and
hence concluded that the result of a launder_invariant_group call cannot alias
any local non-escaping value."
The first attempt to fix it fixed BasicAA
(rL332466<https://reviews.llvm.org/rL332466>), but apparently there were
similar issues in other parts. These were fixed by
rL333070<https://reviews.llvm.org/rL333070>.

Another example is our downstream optimization which does some sort of scalar
replacement of non-escaping allocations. It rewrites uses of the allocation and
needs to know about "aliases" as their uses also need to be rewritten.
Currently
it knows about all the "aliases" supported by CT, but it's not
resilient to
further changes in CT.

Proposal

Currently CaptureTracker is notified about capturing uses through
CaptureTracker::captured. I propose to notify the tracker about all the uses
explicitly specifying the kind (NoCapture, Alias, Capture). This way the tracker
can only accept Alias uses it knows how to handle. If something unexpected comes
up the tracker can give up the analysis.

The default tracker can ignore Alias uses under the assumption that upstream
users of CT maintain tight coupling with the analysis, like it is today.
Refactoring of upstream users of CT is out of scope for this proposal. But in
future they can be decoupled from CT implementation by explicitly checking the
Alias uses.

Can you elaborate on how this makes the handling of special intrinsics, etc.
easier to maintain? I certainly agree that the launder_invariant_group coupling
seems unfortunate, but seemed to me to be a special case (and it is an intrinsic
designed to have special aliasing properties).

 -Hal

Thoughts?

Artur



_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


--
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/20190105/8e60f415/attachment-0001.html>

On 4 Jan 2019, at 16:39, Finkel, Hal J. <hfinkel at anl.gov<mailto:hfinkel
at anl.gov>> wrote:



On 1/4/19 5:24 PM, Artur Pilipenko via llvm-dev wrote:
Working on a downstream optimization which uses CaptureTracking (CT) I came
across a coupling problem. It looks like optimizations and analyses which use CT
often need to be in sync with CT implementation.

Analyzing the uses of the given pointer CT handles three kinds of uses:
 * Simple non-capturing use. When one is encountered, CT just moves on.
 * Non-capturing, but produces another value, which needs to be tracked.
   Examples: bitcasts, geps, phis, selects, etc. I’ll call this kind of uses
   "aliases", for the lack of better word.
 * Capturing.

The "aliases" are tricky. CT users often need to know about these. For
example,
rL331587<https://reviews.llvm.org/rL331587> taught CT the
"alias" semantic of launder.invariant.group calls.
Because BasicAA was not aware of this change, it lead to incorrect AA results.
"BasicAA still considered every call instruction as a possible escape
source and
hence concluded that the result of a launder_invariant_group call cannot alias
any local non-escaping value."
The first attempt to fix it fixed BasicAA
(rL332466<https://reviews.llvm.org/rL332466>), but apparently there were
similar issues in other parts. These were fixed by
rL333070<https://reviews.llvm.org/rL333070>.

Another example is our downstream optimization which does some sort of scalar
replacement of non-escaping allocations. It rewrites uses of the allocation and
needs to know about "aliases" as their uses also need to be rewritten.
Currently
it knows about all the "aliases" supported by CT, but it's not
resilient to
further changes in CT.

Proposal

Currently CaptureTracker is notified about capturing uses through
CaptureTracker::captured. I propose to notify the tracker about all the uses
explicitly specifying the kind (NoCapture, Alias, Capture). This way the tracker
can only accept Alias uses it knows how to handle. If something unexpected comes
up the tracker can give up the analysis.

The default tracker can ignore Alias uses under the assumption that upstream
users of CT maintain tight coupling with the analysis, like it is today.
Refactoring of upstream users of CT is out of scope for this proposal. But in
future they can be decoupled from CT implementation by explicitly checking the
Alias uses.

Can you elaborate on how this makes the handling of special intrinsics, etc.
easier to maintain? I certainly agree that the launder_invariant_group coupling
seems unfortunate, but seemed to me to be a special case (and it is an intrinsic
designed to have special aliasing properties).

Currently there is an implicit dependency: CT clients should know to look though
all "alias" uses known to CT. If the dependency is not satisfied, the
result is
a subtle miscompile. The proposal is to notify CT clients about
"alias" uses,
which gives them a chance to give up the analysis if an unexpected use comes up.

It doesn't eliminate the need to teach the optimizations about new
"aliases"
added to CT. What it does, it turns a miscompile into a missed optimization.

To give an example, let's say we had had this mechanism implemented before
we
taught launder_invariant_group semantic to CT. CT clients which need to look
though CT "aliases" would have used a custom tracker which checks the
aliases
explicitly:

  bool CaptureTracker::notifyUse(Use *U, UseKind Kind) {
    if (Kind == Alias)
      if (U->getUser() is not supported type)
        return false; // Terminate the analysis
  }

Introduction of a new launder_invariant_group "alias" wouldn't
have resulted in
miscompiles because the clients which didn't expect it as an alias would
have
conservatively treated it as a capture.

Artur

 -Hal

Thoughts?

Artur



_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


--
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/20190105/dcd3db54/attachment.html>