llvm dev - Dec 2015 - RFC: New function attribute HasInaccessibleState

Vaivaswatha Nagaraj via llvm-dev wrote:
 >  >I'm against adding this as a "subtractive" attribute.
We need to add these as new attributes, not as an attribute that
 > makes readonly a little less read only. I believe we're in agreement
on this point.
 > Just to make sure I understood right, below are the things that need to be
done:
 > (Approach A)
 > 1. We define a new a attribute "HasInaccessibleState" to denote
"this function might access globals, but none of these
 > globals can alias with any memory location accessible from the IR being
optimized".
 > 2. Mark malloc/free as  (HasInaccessibleState, ReadNone) and printf as
(HasInaccessibleState, ArgMemOnly) ... (similarly
 > other libc functions).

You'll have to mark free as argmemonly + read-write, since the
following transform needs to be illegal:

   val = *ptr
   free(ptr)

=>

  free(ptr)
  val = *ptr

In fact, I think you can mark @free as argmemonly *today* without any
problems.  There is a theoretical issue on whether a "write" can make
a location no longer dereferenceable, but that's not new.

 > 3. Any function whose definition is not available needs to be marked with
"HasInaccessibleState" (conservatively).
 > 4. Propagate the flag "HasInaccessibleState" upwards in the call
graph. (Do this in FunctionAttrs.cpp?).
 > 5. Since ReadNone and ArgMemOnly has now been redfined, all optimizations
that rely on these flags for safety now also
 > need to check the new "HasInaccessibleState" flag and make sure
it isn't present.
 > 6. GlobalsAA will be modified according to the diff in the first mail in
this email thread.
 >
 > The alternative approach that was discussed would involve the following
changes:
 > (Approach B)
 > 1. Define new attributes AlmostReadNone and AlmostArgMemOnly, (with the
"Almost" part denoting that the function may
 > accesses globals that are not part of the IR).
 > 2. malloc/free would have AlmostReadNone set and printf would have
AlmostArgMemOnly set ... (and similarly other libc
 > calls).
 > 3. In the diff I originally posted for GlobalsAA, the code would check for
AlmostReadNone or AlmostArgMemOnly too (along
 > with ReadNone or ArgMemOnly).
 >
 > Approach B seems simpler to me, but I understand the concern about having
a "subtractive" attribute which is new to the
 > framework. If there is a consensus on which of these two approaches is the
way to go, I can submit a quick prototype
 > patch for further review/discussion.

A third approach is to extend the noalias metadata [1] (I mentioned
this earlier in the thread, but did not do a good job on
expanding on it).  Currently noalias metadata can be used to specify
that a certain call or invoke does not read / modify memory locations
belonging to certain *specific* alias domains.  We could generalize
this mechanism and specify a new kind of alias domain called (say)
!ir-mem.  Calls to @malloc and @printf could be marked with "!noalias
!ir-mem" [2], and we could specify (as an axiom) that no loads and
stores visible at the IR level alias with the !ir-mem domain.  The
advantage of this approach is that we won't have to introduce any
fundamentally new first class concepts to LLVM IR (though it would
still be a fair amount of work).

[1]: http://llvm.org/docs/LangRef.html#noalias-and-alias-scope-metadata
[2]: We'll also have to introduce an "NoAliasIRMem" attribute,
that
can be used denote that all calls to the marked function are !noalias
!ir-mem.

-- Sanjoy


 >
 > Thanks,
 >
 >
 >    - Vaivaswatha
 >
 > On Sat, Dec 12, 2015 at 3:21 AM, Hal Finkel via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>
wrote:
 >
 >     ----- Original Message -----
 >     >  From: "Joseph Tremoulet" <jotrem at microsoft.com
<mailto:jotrem at microsoft.com>>
 >     >  To: "Hal Finkel" <hfinkel at anl.gov
<mailto:hfinkel at anl.gov>>, "Mehdi Amini" <mehdi.amini
at apple.com
 >     <mailto:mehdi.amini at apple.com>>
 >     >  Cc: "llvm-dev" <llvm-dev at lists.llvm.org
<mailto:llvm-dev at lists.llvm.org>>
 >     >  Sent: Friday, December 11, 2015 3:35:38 PM
 >     >  Subject: RE: [llvm-dev] RFC: New function attribute
HasInaccessibleState
 >     >
 >     >  Yeah, I'd agree (rewording slightly) that "state which
is only
 >     >  modified by external code" is well-defined (and likely to
be in the
 >     >  "other" bucket of any individual analysis).  I do, as
other have,
 >     >  find it odd to redefine readonly and argmemonly in terms of this
and
 >     >  require its propagation up the call graph, as opposed to
introducing
 >     >  new "writes only external" and "writes only arg
and external"
 >     >  attributes.
 >
 >     As I stated in some other e-mail, I'm against adding this as a
"subtractive" attribute. We need to add these as new
 >     attributes, not as an attribute that makes readonly a little less read
only. I believe we're in agreement on this
point.
 >
 >       -Hal
 >
 >      >
 >      > Thanks
 >      > -Joseph
 >      >
 >      > -----Original Message-----
 >      > From: Hal Finkel [mailto:hfinkel at anl.gov <mailto:hfinkel
at anl.gov>]
 >      > Sent: Friday, December 11, 2015 4:00 PM
 >      > To: Mehdi Amini <mehdi.amini at apple.com
<mailto:mehdi.amini at apple.com>>
 >      > Cc: llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev
at lists.llvm.org>>; Joseph Tremoulet
 >      > <jotrem at microsoft.com <mailto:jotrem at
microsoft.com>>
 >      > Subject: Re: [llvm-dev] RFC: New function attribute
 >      > HasInaccessibleState
 >      >
 >      > ----- Original Message -----
 >      > > From: "Mehdi Amini" <mehdi.amini at apple.com
<mailto:mehdi.amini at apple.com>>
 >      > > To: "Joseph Tremoulet" <jotrem at
microsoft.com <mailto:jotrem at microsoft.com>>
 >      > > Cc: "Hal Finkel" <hfinkel at anl.gov
<mailto:hfinkel at anl.gov>>, "llvm-dev"
 >      > > <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>>
 >      > > Sent: Friday, December 11, 2015 1:28:05 PM
 >      > > Subject: Re: [llvm-dev] RFC: New function attribute
 >      > > HasInaccessibleState
 >      > >
 >      > >
 >      > > > On Dec 11, 2015, at 11:16 AM, Joseph Tremoulet
 >      > > > <jotrem at microsoft.com <mailto:jotrem at
microsoft.com>> wrote:
 >      > > >
 >      > > > <<<
 >      > > > I may misunderstand, but it seems to me that this
solves only
 >      > > > query
 >      > > > for aliasing with a pointer known to be pointing only
to globals
 >      > > > defined in the current compilation unit.
 >      > > > For any pointer which "may point somewhere else”,
you won’t be
 >      > > > able
 >      > > > to resolve the non-aliasing with the “internal state”
for
 >      > > > malloc/free, right?
 >      > > >
 >      > > > To take the original example in this thread:
 >      > > >
 >      > > > int *x = malloc(4);
 >      > > > *x = 2;
 >      > > > int *y = malloc(4);
 >      > > > *y = 4;
 >      > > >
 >      > > > A pointer analysis can solve this case, but I’m not
sure it scale
 >      > > > inter procedurally and will have a limited impact
outside of LTO
 >      > > > anyway.
 >      > > >>>>
 >      > > >
 >      > > > I think you're understanding correctly, but I
don't understand
 >      > > > what
 >      > > > you're saying will go badly with the malloc
example.  Quoting the
 >      > > > start of the thread:
 >      > > >
 >      > > > <<<
 >      > > > The intention behind introducing this attribute is to
relax the
 >      > > > conditions in GlobalsAA as below:
 >      > > > (this code is in GlobalsAAResult::AnalyzeCallGraph)
 >      > > >       if (F->isDeclaration()) {
 >      > > >         // Try to get mod/ref behaviour from function
attributes.
 >      > > > -        if (F->doesNotAccessMemory()) {
 >      > > > +        if (F->doesNotAccessMemory() ||
 >      > > > F->onlyAccessesArgMemory()) {
 >      > > >           // Can't do better than that!
 >      > > >         } else if (F->onlyReadsMemory()) {
 >      > > >           FunctionEffect |= Ref;
 >      > > >           if (!F->isIntrinsic())
 >      > > >             // This function might call back into the
module and
 >      > > >             read a global -
 >      > > >             // consider every global as possibly being
read by
 >      > > >             this
 >      > > >             function.
 >      > > >             FR.MayReadAnyGlobal = true;
 >      > > >         } else {
 >      > > >           FunctionEffect |= ModRef;
 >      > > >           // Can't say anything useful unless
it's an intrinsic -
 >      > > >           they don't
 >      > > >           // read or write global variables of the
kind
 >      > > >           considered
 >      > > >           here.
 >      > > >           KnowNothing = !F->isIntrinsic();
 >      > > >         }
 >      > > >         continue;
 >      > > >       }
 >      > > > This relaxation allows functions that (transitively)
call library
 >      > > > functions (such as printf/malloc) to still maintain
and propagate
 >      > > > GlobalsAA info. In general, this adds more precision
to the
 >      > > > description of these functions.
 >      > > > Concerns regarding impact on other optimizations
(I'm repeating a
 >      > > > few examples that Hal mentioned earlier).
 >      > > >
 >      > > > 1.
 >      > > >> A readnone function is one whose output is a
function only of
 >      > > >> its
 >      > > >> inputs, and if you have this:
 >      > > >>
 >      > > >> int *x = malloc(4);
 >      > > >> *x = 2;
 >      > > >> int *y = malloc(4);
 >      > > >> *y = 4;
 >      > > >> you certainly don't want EarlyCSE to replace
the second call to
 >      > > >> malloc with the result of the first (which it will
happily do if
 >      > > >> you mark malloc as readnone).
 >      > > >>>>
 >      > > >
 >      > > > It sounded like improving GlobalsAA (and thus
disambiguation
 >      > > > against
 >      > > > globals) was the explicit goal, and that the concern
with the
 >      > > > malloc
 >      > > > case was that you don't want EarlyCSE to start
combining those
 >      > > > two
 >      > > > calls; I may be misunderstanding the code, but I
wouldn't expect
 >      > > > EarlyCSE to start combining those calls just because
they have a
 >      > > > new
 >      > > > meaningful-only-to-GlobalsAA
"almost-readnone" attribute.
 >      > >
 >      > > Sure, my point is not that your solution would enable CSE
where we
 >      > > don’t want, but rather that it is not as powerful as what
the
 >      > > attribute “HasInaccessibleState” would model, which I saw
as "this
 >      > > function might access globals, but none of these globals
can alias
 >      > > with any memory location accessible from the IR being
optimized”.
 >      >
 >      > This is also, essentially, what I had in mind. I think it is
 >      > sufficiently well defined in this form.
 >      >
 >      >  -Hal
 >      >
 >      > > For instance:
 >      > >
 >      > > void foo(int *x) {
 >      > >   int *y = malloc(4);
 >      > >   *x = 2;
 >      > > }
 >      > >
 >      > > If you don’t know anything about x, can you execute the
write to *x
 >      > > before the call to malloc?
 >      > > This is something that the HasInaccessibleState would
allow, but I
 >      > > don’t believe would be possible with your categorization.
 >      > >
 >      > > I’m don’t know how much it matters in practice, but I’d
rather be
 >      > > sure
 >      > > we’re on the same track about the various tradeoff.
 >      > >
 >      > > —
 >      > > Mehdi
 >      > >
 >      > >
 >      > >
 >      > > >
 >      > > >
 >      > > > To the larger point of whether there are other similar
cases that
 >      > > > extending GlobalsAA wouldn't allow us to optimize
-- yes,
 >      > > > certainly.
 >      > > > I'm just saying that I think that the notion of
"external state"
 >      > > > is
 >      > > > much easier to define in the context of a particular
analysis
 >      > > > than
 >      > > > the IR as a whole, and that I'd expect that
coordinating the
 >      > > > notion
 >      > > > across analyses would require methods on the analysis
API
 >      > > > explicitly
 >      > > > for that coordination.
 >      > > >
 >      > > >
 >      > > >
 >      > > > —
 >      > > > Mehdi
 >      > > >
 >      > >
 >      > >
 >      >
 >      > --
 >      > Hal Finkel
 >      > Assistant Computational Scientist
 >      > Leadership Computing Facility
 >      > Argonne National Laboratory
 >      >
 >
 >     --
 >     Hal Finkel
 >     Assistant Computational Scientist
 >     Leadership Computing Facility
 >     Argonne National Laboratory
 >     _______________________________________________
 >     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
 >
 >
 > _______________________________________________
 > LLVM Developers mailing list
 > llvm-dev at lists.llvm.org
 > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

>You'll have to mark free as argmemonly + read-write, since the
The intention is to say that free can modify the memory pointed to in its
argument. Doesn't ArgMemOnly cover that already? I added ReadNone because
it doesn't modify any global (except for what may escape into it via the
parameter). This definition of ReadNone is slightly different from what has
been followed so far, which is why I mentioned that optimizations relying
on ReadNone must now also check for HasInaccessibleState.

  - Vaivaswatha

On Mon, Dec 14, 2015 at 10:59 AM, Sanjoy Das <sanjoy at
playingwithpointers.com
> wrote:
> Vaivaswatha Nagaraj via llvm-dev wrote:
> >  >I'm against adding this as a "subtractive"
attribute. We need to add
> these as new attributes, not as an attribute that
> > makes readonly a little less read only. I believe we're in
agreement on
> this point.
> > Just to make sure I understood right, below are the things that need
to
> be done:
> > (Approach A)
> > 1. We define a new a attribute "HasInaccessibleState" to
denote "this
> function might access globals, but none of these
> > globals can alias with any memory location accessible from the IR
being
> optimized".
> > 2. Mark malloc/free as  (HasInaccessibleState, ReadNone) and printf as
> (HasInaccessibleState, ArgMemOnly) ... (similarly
> > other libc functions).
>
> You'll have to mark free as argmemonly + read-write, since the
> following transform needs to be illegal:
>
>   val = *ptr
>   free(ptr)
>
> =>
>
>  free(ptr)
>  val = *ptr
>
> In fact, I think you can mark @free as argmemonly *today* without any
> problems.  There is a theoretical issue on whether a "write" can
make
> a location no longer dereferenceable, but that's not new.
>
> > 3. Any function whose definition is not available needs to be marked
> with "HasInaccessibleState" (conservatively).
> > 4. Propagate the flag "HasInaccessibleState" upwards in the
call graph.
> (Do this in FunctionAttrs.cpp?).
> > 5. Since ReadNone and ArgMemOnly has now been redfined, all
> optimizations that rely on these flags for safety now also
> > need to check the new "HasInaccessibleState" flag and make
sure it isn't
> present.
> > 6. GlobalsAA will be modified according to the diff in the first mail
in
> this email thread.
> >
> > The alternative approach that was discussed would involve the
following
> changes:
> > (Approach B)
> > 1. Define new attributes AlmostReadNone and AlmostArgMemOnly, (with
the
> "Almost" part denoting that the function may
> > accesses globals that are not part of the IR).
> > 2. malloc/free would have AlmostReadNone set and printf would have
> AlmostArgMemOnly set ... (and similarly other libc
> > calls).
> > 3. In the diff I originally posted for GlobalsAA, the code would check
> for AlmostReadNone or AlmostArgMemOnly too (along
> > with ReadNone or ArgMemOnly).
> >
> > Approach B seems simpler to me, but I understand the concern about
> having a "subtractive" attribute which is new to the
> > framework. If there is a consensus on which of these two approaches is
> the way to go, I can submit a quick prototype
> > patch for further review/discussion.
>
> A third approach is to extend the noalias metadata [1] (I mentioned
> this earlier in the thread, but did not do a good job on
> expanding on it).  Currently noalias metadata can be used to specify
> that a certain call or invoke does not read / modify memory locations
> belonging to certain *specific* alias domains.  We could generalize
> this mechanism and specify a new kind of alias domain called (say)
> !ir-mem.  Calls to @malloc and @printf could be marked with "!noalias
> !ir-mem" [2], and we could specify (as an axiom) that no loads and
> stores visible at the IR level alias with the !ir-mem domain.  The
> advantage of this approach is that we won't have to introduce any
> fundamentally new first class concepts to LLVM IR (though it would
> still be a fair amount of work).
>
> [1]: http://llvm.org/docs/LangRef.html#noalias-and-alias-scope-metadata
> [2]: We'll also have to introduce an "NoAliasIRMem"
attribute, that
> can be used denote that all calls to the marked function are !noalias
> !ir-mem.
>
> -- Sanjoy
>
>
> >
> > Thanks,
> >
> >
> >    - Vaivaswatha
> >
> > On Sat, Dec 12, 2015 at 3:21 AM, Hal Finkel via llvm-dev <
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>
wrote:
> >
> >     ----- Original Message -----
> >     >  From: "Joseph Tremoulet" <jotrem at
microsoft.com <mailto:
> jotrem at microsoft.com>>
> >     >  To: "Hal Finkel" <hfinkel at anl.gov
<mailto:hfinkel at anl.gov>>,
> "Mehdi Amini" <mehdi.amini at apple.com
> >     <mailto:mehdi.amini at apple.com>>
> >     >  Cc: "llvm-dev" <llvm-dev at lists.llvm.org
<mailto:
> llvm-dev at lists.llvm.org>>
> >     >  Sent: Friday, December 11, 2015 3:35:38 PM
> >     >  Subject: RE: [llvm-dev] RFC: New function attribute
> HasInaccessibleState
> >     >
> >     >  Yeah, I'd agree (rewording slightly) that "state
which is only
> >     >  modified by external code" is well-defined (and likely
to be in
> the
> >     >  "other" bucket of any individual analysis).  I do,
as other have,
> >     >  find it odd to redefine readonly and argmemonly in terms of
this
> and
> >     >  require its propagation up the call graph, as opposed to
> introducing
> >     >  new "writes only external" and "writes only
arg and external"
> >     >  attributes.
> >
> >     As I stated in some other e-mail, I'm against adding this as a
> "subtractive" attribute. We need to add these as new
> >     attributes, not as an attribute that makes readonly a little less
> read only. I believe we're in agreement on this point.
> >
> >       -Hal
> >
> >      >
> >      > Thanks
> >      > -Joseph
> >      >
> >      > -----Original Message-----
> >      > From: Hal Finkel [mailto:hfinkel at anl.gov
<mailto:hfinkel at anl.gov
> >]
> >      > Sent: Friday, December 11, 2015 4:00 PM
> >      > To: Mehdi Amini <mehdi.amini at apple.com <mailto:
> mehdi.amini at apple.com>>
> >      > Cc: llvm-dev <llvm-dev at lists.llvm.org <mailto:
> llvm-dev at lists.llvm.org>>; Joseph Tremoulet
> >      > <jotrem at microsoft.com <mailto:jotrem at
microsoft.com>>
> >      > Subject: Re: [llvm-dev] RFC: New function attribute
> >      > HasInaccessibleState
> >      >
> >      > ----- Original Message -----
> >      > > From: "Mehdi Amini" <mehdi.amini at
apple.com <mailto:
> mehdi.amini at apple.com>>
> >      > > To: "Joseph Tremoulet" <jotrem at
microsoft.com <mailto:
> jotrem at microsoft.com>>
> >      > > Cc: "Hal Finkel" <hfinkel at anl.gov
<mailto:hfinkel at anl.gov>>,
> "llvm-dev"
> >      > > <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>>
> >      > > Sent: Friday, December 11, 2015 1:28:05 PM
> >      > > Subject: Re: [llvm-dev] RFC: New function attribute
> >      > > HasInaccessibleState
> >      > >
> >      > >
> >      > > > On Dec 11, 2015, at 11:16 AM, Joseph Tremoulet
> >      > > > <jotrem at microsoft.com <mailto:jotrem at
microsoft.com>> wrote:
> >      > > >
> >      > > > <<<
> >      > > > I may misunderstand, but it seems to me that this
solves only
> >      > > > query
> >      > > > for aliasing with a pointer known to be pointing
only to
> globals
> >      > > > defined in the current compilation unit.
> >      > > > For any pointer which "may point somewhere
else”, you won’t be
> >      > > > able
> >      > > > to resolve the non-aliasing with the “internal
state” for
> >      > > > malloc/free, right?
> >      > > >
> >      > > > To take the original example in this thread:
> >      > > >
> >      > > > int *x = malloc(4);
> >      > > > *x = 2;
> >      > > > int *y = malloc(4);
> >      > > > *y = 4;
> >      > > >
> >      > > > A pointer analysis can solve this case, but I’m
not sure it
> scale
> >      > > > inter procedurally and will have a limited impact
outside of
> LTO
> >      > > > anyway.
> >      > > >>>>
> >      > > >
> >      > > > I think you're understanding correctly, but I
don't understand
> >      > > > what
> >      > > > you're saying will go badly with the malloc
example.  Quoting
> the
> >      > > > start of the thread:
> >      > > >
> >      > > > <<<
> >      > > > The intention behind introducing this attribute is
to relax
> the
> >      > > > conditions in GlobalsAA as below:
> >      > > > (this code is in
GlobalsAAResult::AnalyzeCallGraph)
> >      > > >       if (F->isDeclaration()) {
> >      > > >         // Try to get mod/ref behaviour from
function
> attributes.
> >      > > > -        if (F->doesNotAccessMemory()) {
> >      > > > +        if (F->doesNotAccessMemory() ||
> >      > > > F->onlyAccessesArgMemory()) {
> >      > > >           // Can't do better than that!
> >      > > >         } else if (F->onlyReadsMemory()) {
> >      > > >           FunctionEffect |= Ref;
> >      > > >           if (!F->isIntrinsic())
> >      > > >             // This function might call back into
the module
> and
> >      > > >             read a global -
> >      > > >             // consider every global as possibly
being read by
> >      > > >             this
> >      > > >             function.
> >      > > >             FR.MayReadAnyGlobal = true;
> >      > > >         } else {
> >      > > >           FunctionEffect |= ModRef;
> >      > > >           // Can't say anything useful unless
it's an
> intrinsic -
> >      > > >           they don't
> >      > > >           // read or write global variables of the
kind
> >      > > >           considered
> >      > > >           here.
> >      > > >           KnowNothing = !F->isIntrinsic();
> >      > > >         }
> >      > > >         continue;
> >      > > >       }
> >      > > > This relaxation allows functions that
(transitively) call
> library
> >      > > > functions (such as printf/malloc) to still
maintain and
> propagate
> >      > > > GlobalsAA info. In general, this adds more
precision to the
> >      > > > description of these functions.
> >      > > > Concerns regarding impact on other optimizations
(I'm
> repeating a
> >      > > > few examples that Hal mentioned earlier).
> >      > > >
> >      > > > 1.
> >      > > >> A readnone function is one whose output is a
function only of
> >      > > >> its
> >      > > >> inputs, and if you have this:
> >      > > >>
> >      > > >> int *x = malloc(4);
> >      > > >> *x = 2;
> >      > > >> int *y = malloc(4);
> >      > > >> *y = 4;
> >      > > >> you certainly don't want EarlyCSE to
replace the second call
> to
> >      > > >> malloc with the result of the first (which it
will happily
> do if
> >      > > >> you mark malloc as readnone).
> >      > > >>>>
> >      > > >
> >      > > > It sounded like improving GlobalsAA (and thus
disambiguation
> >      > > > against
> >      > > > globals) was the explicit goal, and that the
concern with the
> >      > > > malloc
> >      > > > case was that you don't want EarlyCSE to start
combining those
> >      > > > two
> >      > > > calls; I may be misunderstanding the code, but I
wouldn't
> expect
> >      > > > EarlyCSE to start combining those calls just
because they
> have a
> >      > > > new
> >      > > > meaningful-only-to-GlobalsAA
"almost-readnone" attribute.
> >      > >
> >      > > Sure, my point is not that your solution would enable
CSE where
> we
> >      > > don’t want, but rather that it is not as powerful as
what the
> >      > > attribute “HasInaccessibleState” would model, which I
saw as
> "this
> >      > > function might access globals, but none of these
globals can
> alias
> >      > > with any memory location accessible from the IR being
> optimized”.
> >      >
> >      > This is also, essentially, what I had in mind. I think it is
> >      > sufficiently well defined in this form.
> >      >
> >      >  -Hal
> >      >
> >      > > For instance:
> >      > >
> >      > > void foo(int *x) {
> >      > >   int *y = malloc(4);
> >      > >   *x = 2;
> >      > > }
> >      > >
> >      > > If you don’t know anything about x, can you execute the
write
> to *x
> >      > > before the call to malloc?
> >      > > This is something that the HasInaccessibleState would
allow,
> but I
> >      > > don’t believe would be possible with your
categorization.
> >      > >
> >      > > I’m don’t know how much it matters in practice, but I’d
rather
> be
> >      > > sure
> >      > > we’re on the same track about the various tradeoff.
> >      > >
> >      > > —
> >      > > Mehdi
> >      > >
> >      > >
> >      > >
> >      > > >
> >      > > >
> >      > > > To the larger point of whether there are other
similar cases
> that
> >      > > > extending GlobalsAA wouldn't allow us to
optimize -- yes,
> >      > > > certainly.
> >      > > > I'm just saying that I think that the notion
of "external
> state"
> >      > > > is
> >      > > > much easier to define in the context of a
particular analysis
> >      > > > than
> >      > > > the IR as a whole, and that I'd expect that
coordinating the
> >      > > > notion
> >      > > > across analyses would require methods on the
analysis API
> >      > > > explicitly
> >      > > > for that coordination.
> >      > > >
> >      > > >
> >      > > >
> >      > > > —
> >      > > > Mehdi
> >      > > >
> >      > >
> >      > >
> >      >
> >      > --
> >      > Hal Finkel
> >      > Assistant Computational Scientist
> >      > Leadership Computing Facility
> >      > Argonne National Laboratory
> >      >
> >
> >     --
> >     Hal Finkel
> >     Assistant Computational Scientist
> >     Leadership Computing Facility
> >     Argonne National Laboratory
> >     _______________________________________________
> >     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
>
> >
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151214/d88e602d/attachment-0001.html>

Vaivaswatha Nagaraj wrote:
>  >You'll have to mark free as argmemonly + read-write, since the
> The intention is to say that free can modify the memory pointed to in its
argument. Doesn't ArgMemOnly cover that
> already?
Yes, but I thought you were suggesting against marking free as argmemonly, since
you said "Mark malloc/free as
(HasInaccessibleState, ReadNone)"?

A question that will help me assess if I've understood what you have in
mind:  why do you need to mark printf() as
argmemonly?

-- Sanjoy
>
>    - Vaivaswatha
>
> On Mon, Dec 14, 2015 at 10:59 AM, Sanjoy Das <sanjoy at
playingwithpointers.com <mailto:sanjoy at playingwithpointers.com>>
wrote:
>
>     Vaivaswatha Nagaraj via llvm-dev wrote:
>     >  >I'm against adding this as a "subtractive"
attribute. We need to add these as new attributes, not as an attribute
>     that
>     >  makes readonly a little less read only. I believe we're in
agreement on this point.
>     >  Just to make sure I understood right, below are the things that
need to be done:
>     >  (Approach A)
>     >  1. We define a new a attribute "HasInaccessibleState"
to denote "this function might access globals, but none of these
>     >  globals can alias with any memory location accessible from the IR
being optimized".
>     >  2. Mark malloc/free as  (HasInaccessibleState, ReadNone) and
printf as (HasInaccessibleState, ArgMemOnly) ...
>     (similarly
>     >  other libc functions).
>
>     You'll have to mark free as argmemonly + read-write, since the
>     following transform needs to be illegal:
>
>        val = *ptr
>        free(ptr)
>
>     =>
>
>       free(ptr)
>       val = *ptr
>
>     In fact, I think you can mark @free as argmemonly *today* without any
>     problems.  There is a theoretical issue on whether a "write"
can make
>     a location no longer dereferenceable, but that's not new.
>
>     >  3. Any function whose definition is not available needs to be
marked with "HasInaccessibleState" (conservatively).
>     >  4. Propagate the flag "HasInaccessibleState" upwards in
the call graph. (Do this in FunctionAttrs.cpp?).
>     >  5. Since ReadNone and ArgMemOnly has now been redfined, all
optimizations that rely on these flags for safety now also
>     >  need to check the new "HasInaccessibleState" flag and
make sure it isn't present.
>     >  6. GlobalsAA will be modified according to the diff in the first
mail in this email thread.
>     >
>     >  The alternative approach that was discussed would involve the
following changes:
>     >  (Approach B)
>     >  1. Define new attributes AlmostReadNone and AlmostArgMemOnly,
(with the "Almost" part denoting that the function may
>     >  accesses globals that are not part of the IR).
>     >  2. malloc/free would have AlmostReadNone set and printf would
have AlmostArgMemOnly set ... (and similarly other libc
>     >  calls).
>     >  3. In the diff I originally posted for GlobalsAA, the code would
check for AlmostReadNone or AlmostArgMemOnly too
>     (along
>     >  with ReadNone or ArgMemOnly).
>     >
>     >  Approach B seems simpler to me, but I understand the concern
about having a "subtractive" attribute which is new
>     to the
>     >  framework. If there is a consensus on which of these two
approaches is the way to go, I can submit a quick prototype
>     >  patch for further review/discussion.
>
>     A third approach is to extend the noalias metadata [1] (I mentioned
>     this earlier in the thread, but did not do a good job on
>     expanding on it).  Currently noalias metadata can be used to specify
>     that a certain call or invoke does not read / modify memory locations
>     belonging to certain *specific* alias domains.  We could generalize
>     this mechanism and specify a new kind of alias domain called (say)
>     !ir-mem.  Calls to @malloc and @printf could be marked with
"!noalias
>     !ir-mem" [2], and we could specify (as an axiom) that no loads and
>     stores visible at the IR level alias with the !ir-mem domain.  The
>     advantage of this approach is that we won't have to introduce any
>     fundamentally new first class concepts to LLVM IR (though it would
>     still be a fair amount of work).
>
>     [1]: http://llvm.org/docs/LangRef.html#noalias-and-alias-scope-metadata
>     [2]: We'll also have to introduce an "NoAliasIRMem"
attribute, that
>     can be used denote that all calls to the marked function are !noalias
>     !ir-mem.
>
>     -- Sanjoy
>
>
>      >
>      > Thanks,
>      >
>      >
>      >    - Vaivaswatha
>     >
>     >  On Sat, Dec 12, 2015 at 3:21 AM, Hal Finkel via llvm-dev
<llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>     <mailto:llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>>> wrote:
>     >
>     >      ----- Original Message -----
>     >  >  From: "Joseph Tremoulet" <jotrem at
microsoft.com <mailto:jotrem at microsoft.com> <mailto:jotrem at
microsoft.com
>     <mailto:jotrem at microsoft.com>>>
>     >  >  To: "Hal Finkel" <hfinkel at anl.gov
<mailto:hfinkel at anl.gov> <mailto:hfinkel at anl.gov
<mailto:hfinkel at anl.gov>>>,
>     "Mehdi Amini" <mehdi.amini at apple.com
<mailto:mehdi.amini at apple.com>
>     >  <mailto:mehdi.amini at apple.com <mailto:mehdi.amini at
apple.com>>>
>     >  >  Cc: "llvm-dev" <llvm-dev at lists.llvm.org
<mailto:llvm-dev at lists.llvm.org> <mailto:llvm-dev at lists.llvm.org
>     <mailto:llvm-dev at lists.llvm.org>>>
>     >  >  Sent: Friday, December 11, 2015 3:35:38 PM
>     >  >  Subject: RE: [llvm-dev] RFC: New function attribute
HasInaccessibleState
>     >  >
>     >  >  Yeah, I'd agree (rewording slightly) that "state
which is only
>     >  >  modified by external code" is well-defined (and likely
to be in the
>     >  > "other" bucket of any individual analysis).  I do,
as other have,
>     >  >  find it odd to redefine readonly and argmemonly in terms of
this and
>     >  >  require its propagation up the call graph, as opposed to
introducing
>     >  >  new "writes only external" and "writes only
arg and external"
>     >  >  attributes.
>     >
>     >      As I stated in some other e-mail, I'm against adding this
as a "subtractive" attribute. We need to add these
>     as new
>     >      attributes, not as an attribute that makes readonly a little
less read only. I believe we're in agreement on
>     this point.
>     >
>     >        -Hal
>     >
>     >  >
>     >  > Thanks
>     >  > -Joseph
>     >  >
>     >  > -----Original Message-----
>     >  > From: Hal Finkel [mailto:hfinkel at anl.gov
<mailto:hfinkel at anl.gov> <mailto:hfinkel at anl.gov
<mailto:hfinkel at anl.gov>>]
>     >  > Sent: Friday, December 11, 2015 4:00 PM
>     >  > To: Mehdi Amini <mehdi.amini at apple.com
<mailto:mehdi.amini at apple.com> <mailto:mehdi.amini at apple.com
>     <mailto:mehdi.amini at apple.com>>>
>     >  > Cc: llvm-dev <llvm-dev at lists.llvm.org
<mailto:llvm-dev at lists.llvm.org> <mailto:llvm-dev at lists.llvm.org
>     <mailto:llvm-dev at lists.llvm.org>>>; Joseph Tremoulet
>     >  > <jotrem at microsoft.com <mailto:jotrem at
microsoft.com> <mailto:jotrem at microsoft.com <mailto:jotrem at
microsoft.com>>>
>     >  > Subject: Re: [llvm-dev] RFC: New function attribute
>     >  > HasInaccessibleState
>     >  >
>     >  > ----- Original Message -----
>     >  > > From: "Mehdi Amini" <mehdi.amini at
apple.com <mailto:mehdi.amini at apple.com> <mailto:mehdi.amini at
apple.com
>     <mailto:mehdi.amini at apple.com>>>
>     >  > > To: "Joseph Tremoulet" <jotrem at
microsoft.com <mailto:jotrem at microsoft.com> <mailto:jotrem at
microsoft.com
>     <mailto:jotrem at microsoft.com>>>
>     >  > > Cc: "Hal Finkel" <hfinkel at anl.gov
<mailto:hfinkel at anl.gov> <mailto:hfinkel at anl.gov
<mailto:hfinkel at anl.gov>>>,
>     "llvm-dev"
>     >  > > <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org> <mailto:llvm-dev at lists.llvm.org
>     <mailto:llvm-dev at lists.llvm.org>>>
>     >  > > Sent: Friday, December 11, 2015 1:28:05 PM
>     >  > > Subject: Re: [llvm-dev] RFC: New function attribute
>     >  > > HasInaccessibleState
>     >  > >
>     >  > >
>     >  > > > On Dec 11, 2015, at 11:16 AM, Joseph Tremoulet
>      > > > > <jotrem at microsoft.com <mailto:jotrem at
microsoft.com> <mailto:jotrem at microsoft.com
>     <mailto:jotrem at microsoft.com>>> wrote:
>      > > > >
>      > > > > <<<
>      > > > > I may misunderstand, but it seems to me that this
solves only
>      > > > > query
>      > > > > for aliasing with a pointer known to be pointing
only to globals
>      > > > > defined in the current compilation unit.
>      > > > > For any pointer which "may point somewhere
else”, you won’t be
>      > > > > able
>      > > > > to resolve the non-aliasing with the “internal
state” for
>      > > > > malloc/free, right?
>      > > > >
>      > > > > To take the original example in this thread:
>      > > > >
>      > > > > int *x = malloc(4);
>      > > > > *x = 2;
>      > > > > int *y = malloc(4);
>      > > > > *y = 4;
>      > > > >
>      > > > > A pointer analysis can solve this case, but I’m
not sure it scale
>      > > > > inter procedurally and will have a limited impact
outside of LTO
>      > > > > anyway.
>      > > > >>>>
>      > > > >
>      > > > > I think you're understanding correctly, but I
don't understand
>      > > > > what
>      > > > > you're saying will go badly with the malloc
example.  Quoting the
>      > > > > start of the thread:
>      > > > >
>      > > > > <<<
>      > > > > The intention behind introducing this attribute is
to relax the
>      > > > > conditions in GlobalsAA as below:
>      > > > > (this code is in
GlobalsAAResult::AnalyzeCallGraph)
>      > > > >       if (F->isDeclaration()) {
>      > > > >         // Try to get mod/ref behaviour from
function attributes.
>      > > > > -        if (F->doesNotAccessMemory()) {
>      > > > > +        if (F->doesNotAccessMemory() ||
>      > > > > F->onlyAccessesArgMemory()) {
>      > > > >           // Can't do better than that!
>      > > > >         } else if (F->onlyReadsMemory()) {
>      > > > >           FunctionEffect |= Ref;
>      > > > >           if (!F->isIntrinsic())
>      > > > >             // This function might call back into
the module and
>      > > > >             read a global -
>      > > > >             // consider every global as possibly
being read by
>      > > > >             this
>      > > > >             function.
>      > > > >             FR.MayReadAnyGlobal = true;
>      > > > >         } else {
>      > > > >           FunctionEffect |= ModRef;
>      > > > >           // Can't say anything useful unless
it's an intrinsic -
>      > > > >           they don't
>      > > > >           // read or write global variables of the
kind
>      > > > >           considered
>      > > > >           here.
>      > > > >           KnowNothing = !F->isIntrinsic();
>      > > > >         }
>      > > > >         continue;
>      > > > >       }
>      > > > > This relaxation allows functions that
(transitively) call library
>      > > > > functions (such as printf/malloc) to still
maintain and propagate
>      > > > > GlobalsAA info. In general, this adds more
precision to the
>      > > > > description of these functions.
>      > > > > Concerns regarding impact on other optimizations
(I'm repeating a
>      > > > > few examples that Hal mentioned earlier).
>      > > > >
>      > > > > 1.
>      > > > >> A readnone function is one whose output is a
function only of
>      > > > >> its
>      > > > >> inputs, and if you have this:
>      > > > >>
>      > > > >> int *x = malloc(4);
>      > > > >> *x = 2;
>      > > > >> int *y = malloc(4);
>      > > > >> *y = 4;
>      > > > >> you certainly don't want EarlyCSE to
replace the second call to
>      > > > >> malloc with the result of the first (which it
will happily do if
>      > > > >> you mark malloc as readnone).
>      > > > >>>>
>      > > > >
>      > > > > It sounded like improving GlobalsAA (and thus
disambiguation
>      > > > > against
>      > > > > globals) was the explicit goal, and that the
concern with the
>      > > > > malloc
>      > > > > case was that you don't want EarlyCSE to start
combining those
>      > > > > two
>      > > > > calls; I may be misunderstanding the code, but I
wouldn't expect
>      > > > > EarlyCSE to start combining those calls just
because they have a
>      > > > > new
>      > > > > meaningful-only-to-GlobalsAA
"almost-readnone" attribute.
>      > > >
>      > > > Sure, my point is not that your solution would enable
CSE where we
>      > > > don’t want, but rather that it is not as powerful as
what the
>      > > > attribute “HasInaccessibleState” would model, which I
saw as "this
>      > > > function might access globals, but none of these
globals can alias
>      > > > with any memory location accessible from the IR being
optimized”.
>      > >
>      > > This is also, essentially, what I had in mind. I think it is
>      > > sufficiently well defined in this form.
>      > >
>      > >  -Hal
>      > >
>      > > > For instance:
>      > > >
>      > > > void foo(int *x) {
>      > > >   int *y = malloc(4);
>      > > >   *x = 2;
>      > > > }
>      > > >
>      > > > If you don’t know anything about x, can you execute the
write to *x
>      > > > before the call to malloc?
>      > > > This is something that the HasInaccessibleState would
allow, but I
>      > > > don’t believe would be possible with your
categorization.
>      > > >
>      > > > I’m don’t know how much it matters in practice, but I’d
rather be
>      > > > sure
>      > > > we’re on the same track about the various tradeoff.
>      > > >
>      > > > —
>      > > > Mehdi
>      > > >
>      > > >
>      > > >
>      > > > >
>      > > > >
>      > > > > To the larger point of whether there are other
similar cases that
>      > > > > extending GlobalsAA wouldn't allow us to
optimize -- yes,
>      > > > > certainly.
>      > > > > I'm just saying that I think that the notion
of "external state"
>      > > > > is
>      > > > > much easier to define in the context of a
particular analysis
>      > > > > than
>      > > > > the IR as a whole, and that I'd expect that
coordinating the
>      > > > > notion
>      > > > > across analyses would require methods on the
analysis API
>      > > > > explicitly
>      > > > > for that coordination.
>      > > > >
>      > > > >
>      > > > >
>      > > > > —
>      > > > > Mehdi
>      > > > >
>      > > >
>      > > >
>      > >
>      > > --
>      > > Hal Finkel
>      > > Assistant Computational Scientist
>      > > Leadership Computing Facility
>      > > Argonne National Laboratory
>      > >
>      >
>      >     --
>      >     Hal Finkel
>      >     Assistant Computational Scientist
>      >     Leadership Computing Facility
>      >     Argonne National Laboratory
>      >     _______________________________________________
>      >     LLVM Developers mailing list
>      > llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org> <mailto:llvm-dev at lists.llvm.org
>     <mailto:llvm-dev at lists.llvm.org>>
>      > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>      >
>      >
>      > _______________________________________________
>      > 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
>
>