llvm dev - Jan 2015 - [LLVMdev] question about enabling cfl-aa and collecting a57 numbers

> I had thought that the case that Danny had looked at had a constant GEP,
and so this constant might alias with other global pointers. How is that
handled now?
That issue had to do with that we assumed that for all arguments of a given
Instruction, each argument was either an Argument, GlobalValue, or Inst in
`for (auto& Bb : Inst.getBasicBlockList()) for (auto& Inst :
Bb.getInstList())`. ConstantExprs didn't fit into this instruction, because
they aren't reached by said nested loop.

With this fix, if we detect that there's a relevant ConstantExpr, we'll
look into it as if it were a regular Instruction inside of
Bb.getInstList(), which causes us to correctly detect the globals, etc.

(I included a test case specifically for this -- it's ugly, but we have ~3
nested GEPs with a global at the innermost GEP. It produces the appropriate
output)

George

On Fri, Jan 30, 2015 at 10:56 AM, Hal Finkel <hfinkel at anl.gov> wrote:
> ----- Original Message -----
> > From: "George Burgess IV" <george.burgess.iv at
gmail.com>
> > To: "Daniel Berlin" <dberlin at dberlin.org>
> > Cc: "Chandler Carruth" <chandlerc at google.com>,
"Hal Finkel" <
> hfinkel at anl.gov>, "Jiangning Liu"
> > <Jiangning.Liu at arm.com>, "LLVM Developers Mailing
List" <
> llvmdev at cs.uiuc.edu>
> > Sent: Friday, January 30, 2015 8:15:55 AM
> > Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting
a57
> numbers
> >
> >
> >
> > I'm not exactly thrilled about the size of this diff -- I'll
happily
> > break it up into more manageable bits later today, because some of
> > it is test fixes, another bit is a minor bug fix, etc.
>
> Yes, please break it into independent parts.
>
> >
> >
> > Important bit (WRT ConstantExpr): moved the loop body from
> > buildGraphFrom into a new function. The body has a few tweaks to
> > call constexprToEdges on all ConstantExprs that we encounter.
> > constexprToEdges, naturally, interprets a ConstantExpr (and all
> > nested ConstantExprs) and places the results into a
> > SmallVector<Edge>.
> >
> >
> > I'm assuming this method of handling ConstantExprs isn't 100%
correct
> > because I was told that handling them correctly would be more
> > difficult than I think it is. I can't quite figure out why, so
> > examples of cases that break my code would be greatly appreciated.
> > :)
>
> I had thought that the case that Danny had looked at had a constant GEP,
> and so this constant might alias with other global pointers. How is that
> handled now?
>
> Thanks again,
> Hal
>
> >
> >
> > George
> >
> >
> > On Mon, Jan 26, 2015 at 2:43 PM, George Burgess IV <
> > george.burgess.iv at gmail.com > wrote:
> >
> >
> >
> >
> > Inline
> >
> >
> > George
> >
> >
> >
> >
> > On Jan 26, 2015, at 1:05 PM, Daniel Berlin < dberlin at dberlin.org
>
> > wrote:
> >
> >
> > George, given that, can you just build constexpr handling (it's
not
> > as easy as you think) as a separate funciton and have it use it in
> > the right places?
> > Will do. :)
> >
> >
> >
> >
> >
> > FWIW, my current list of CFLAA issues is:
> >
> > 1. Unknown values (results from ptrtoint, incoming pointers, etc) are
> > not treated as unknown. These should be done through graph edge (so
> > that they can be one way, otherwise, you will unify everything :P)
> >
> >
> >
> >
> > 2. Constexpr handling
> >
> >
> >
> >
> > ^^^ These are correctness issues. I'm pretty sure there are a few
> > more but i haven't finished auditing
> > 3. In a number of places we treat non-pointers as memory-locations
> > and unify them with pointers. This introduces a lot of spurious
> > aliasing.
> > 4. More generally, we induce a lot of spurious aliasing through
> > things at different dereference levels. In these cases, one may to
> > the other, but, for example, if we have a foo***, and a foo* (and
> > neither pointers to unknown things or escapes), the only way for foo
> > *** to alias foo* is if there is a graph path with two dereferences
> > between them.
> > We seem to get this wrong sometimes. Agreed on all four. Though
> > naturally it should be fixed, I’d like to see how much of an issue
> > #4 ends up being when we properly deal with #3.
> >
> >
> >
> >
> >
> >
> >
> > On Sun Jan 25 2015 at 6:44:07 PM Chandler Carruth <
> > chandlerc at google.com > wrote:
> >
> >
> >
> >
> >
> >
> > On Sun, Jan 25, 2015 at 6:37 PM, George Burgess IV <
> > george.burgess.iv at gmail.com > wrote:
> >
> >
> > > Fixing that still gives a wrong result, i haven't started to
track
> > > down what *else* is going on here.
> >
> >
> > Running with the attached diff + a modified buildGraphFrom to handle
> > the constexpr GEPs, we seem to flag everything in test2.ll
> > (conservatively) correctly.
> >
> >
> > Is `store` the only place we can expect to see these constexpr
> > analogs, or is just about anywhere fair game?
> >
> >
> > Any Value can be a ConstantExpr, so all operands to instructions are
> > fair game.
> >
> >
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150130/2d4cdae9/attachment.html>

----- Original Message -----
> From: "George Burgess IV" <george.burgess.iv at gmail.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Chandler Carruth" <chandlerc at google.com>,
"Jiangning Liu" <Jiangning.Liu at arm.com>, "LLVM
Developers Mailing
> List" <llvmdev at cs.uiuc.edu>, "Daniel Berlin"
<dberlin at dberlin.org>
> Sent: Friday, January 30, 2015 10:29:07 AM
> Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57
numbers
> 
> 
> > I had thought that the case that Danny had looked at had a constant
> > GEP, and so this constant might alias with other global pointers.
> > How is that handled now?
> That issue had to do with that we assumed that for all arguments of a
> given Instruction, each argument was either an Argument,
> GlobalValue, or Inst in `for (auto& Bb : Inst.getBasicBlockList())
> for (auto& Inst : Bb.getInstList())`. ConstantExprs didn't fit into
> this instruction, because they aren't reached by said nested loop.
> 
> 
> With this fix, if we detect that there's a relevant ConstantExpr,
> we'll look into it as if it were a regular Instruction inside of
> Bb.getInstList(), which causes us to correctly detect the globals,
> etc.
Sounds good.

Thanks!

 -Hal
> 
> 
> (I included a test case specifically for this -- it's ugly, but we
> have ~3 nested GEPs with a global at the innermost GEP. It produces
> the appropriate output)
> 
> 
> George
> 
> 
> On Fri, Jan 30, 2015 at 10:56 AM, Hal Finkel < hfinkel at anl.gov >
> wrote:
> 
> 
> ----- Original Message -----
> > From: "George Burgess IV" < george.burgess.iv at
gmail.com >
> > To: "Daniel Berlin" < dberlin at dberlin.org >
> > Cc: "Chandler Carruth" < chandlerc at google.com >,
"Hal Finkel" <
> > hfinkel at anl.gov >, "Jiangning Liu"
> > < Jiangning.Liu at arm.com >, "LLVM Developers Mailing
List" <
> > llvmdev at cs.uiuc.edu >
> > Sent: Friday, January 30, 2015 8:15:55 AM
> > Subject: Re: [LLVMdev] question about enabling cfl-aa and
> > collecting a57 numbers
> > 
> > 
> > 
> > I'm not exactly thrilled about the size of this diff -- I'll
> > happily
> > break it up into more manageable bits later today, because some of
> > it is test fixes, another bit is a minor bug fix, etc.
> 
> Yes, please break it into independent parts.
> 
> > 
> > 
> > Important bit (WRT ConstantExpr): moved the loop body from
> > buildGraphFrom into a new function. The body has a few tweaks to
> > call constexprToEdges on all ConstantExprs that we encounter.
> > constexprToEdges, naturally, interprets a ConstantExpr (and all
> > nested ConstantExprs) and places the results into a
> > SmallVector<Edge>.
> > 
> > 
> > I'm assuming this method of handling ConstantExprs isn't 100%
> > correct
> > because I was told that handling them correctly would be more
> > difficult than I think it is. I can't quite figure out why, so
> > examples of cases that break my code would be greatly appreciated.
> > :)
> 
> I had thought that the case that Danny had looked at had a constant
> GEP, and so this constant might alias with other global pointers.
> How is that handled now?
> 
> Thanks again,
> Hal
> 
> 
> 
> > 
> > 
> > George
> > 
> > 
> > On Mon, Jan 26, 2015 at 2:43 PM, George Burgess IV <
> > george.burgess.iv at gmail.com > wrote:
> > 
> > 
> > 
> > 
> > Inline
> > 
> > 
> > George
> > 
> > 
> > 
> > 
> > On Jan 26, 2015, at 1:05 PM, Daniel Berlin < dberlin at dberlin.org
>
> > wrote:
> > 
> > 
> > George, given that, can you just build constexpr handling (it's
not
> > as easy as you think) as a separate funciton and have it use it in
> > the right places?
> > Will do. :)
> > 
> > 
> > 
> > 
> > 
> > FWIW, my current list of CFLAA issues is:
> > 
> > 1. Unknown values (results from ptrtoint, incoming pointers, etc)
> > are
> > not treated as unknown. These should be done through graph edge (so
> > that they can be one way, otherwise, you will unify everything :P)
> > 
> > 
> > 
> > 
> > 2. Constexpr handling
> > 
> > 
> > 
> > 
> > ^^^ These are correctness issues. I'm pretty sure there are a few
> > more but i haven't finished auditing
> > 3. In a number of places we treat non-pointers as memory-locations
> > and unify them with pointers. This introduces a lot of spurious
> > aliasing.
> > 4. More generally, we induce a lot of spurious aliasing through
> > things at different dereference levels. In these cases, one may to
> > the other, but, for example, if we have a foo***, and a foo* (and
> > neither pointers to unknown things or escapes), the only way for
> > foo
> > *** to alias foo* is if there is a graph path with two dereferences
> > between them.
> > We seem to get this wrong sometimes. Agreed on all four. Though
> > naturally it should be fixed, I’d like to see how much of an issue
> > #4 ends up being when we properly deal with #3.
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > On Sun Jan 25 2015 at 6:44:07 PM Chandler Carruth <
> > chandlerc at google.com > wrote:
> > 
> > 
> > 
> > 
> > 
> > 
> > On Sun, Jan 25, 2015 at 6:37 PM, George Burgess IV <
> > george.burgess.iv at gmail.com > wrote:
> > 
> > 
> > > Fixing that still gives a wrong result, i haven't started to
> > > track
> > > down what *else* is going on here.
> > 
> > 
> > Running with the attached diff + a modified buildGraphFrom to
> > handle
> > the constexpr GEPs, we seem to flag everything in test2.ll
> > (conservatively) correctly.
> > 
> > 
> > Is `store` the only place we can expect to see these constexpr
> > analogs, or is just about anywhere fair game?
> > 
> > 
> > Any Value can be a ConstantExpr, so all operands to instructions
> > are
> > fair game.
> > 
> > 
> 
> 
> 
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> 
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

So, I split it up into three patches:

- cflaa-danny-fixes.diff are (some of?) the fixes that Danny gave us earlier for
tests + the minimal modifications you’d need to make in CFLAA to make them pass
tests.
- cflaa-minor-bugfixes.diff consists primarily of a bug fix for Argument
handling — we’d always report NoAlias when one of the given variables was an
entirely unused argument
	(We never added the appropriate Argument StratifiedAttr)
- cflaa-constexpr-fix.diff - The fix for the constexpr behavior we’ve been
seeing

Patches are meant to be applied in the order listed.

Also, I just wanted to thank everyone again for your help so far — it’s greatly
appreciated. :)

George
> On Jan 30, 2015, at 11:56 AM, Hal Finkel <hfinkel at anl.gov> wrote:
> 
> ----- Original Message -----
>> From: "George Burgess IV" <george.burgess.iv at gmail.com
<mailto:george.burgess.iv at gmail.com>>
>> To: "Hal Finkel" <hfinkel at anl.gov <mailto:hfinkel at
anl.gov>>
>> Cc: "Chandler Carruth" <chandlerc at google.com
<mailto:chandlerc at google.com>>, "Jiangning Liu"
<Jiangning.Liu at arm.com <mailto:Jiangning.Liu at arm.com>>,
"LLVM Developers Mailing
>> List" <llvmdev at cs.uiuc.edu <mailto:llvmdev at
cs.uiuc.edu>>, "Daniel Berlin" <dberlin at dberlin.org
<mailto:dberlin at dberlin.org>>
>> Sent: Friday, January 30, 2015 10:29:07 AM
>> Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting
a57 numbers
>> 
>> 
>>> I had thought that the case that Danny had looked at had a constant
>>> GEP, and so this constant might alias with other global pointers.
>>> How is that handled now?
>> That issue had to do with that we assumed that for all arguments of a
>> given Instruction, each argument was either an Argument,
>> GlobalValue, or Inst in `for (auto& Bb : Inst.getBasicBlockList())
>> for (auto& Inst : Bb.getInstList())`. ConstantExprs didn't fit
into
>> this instruction, because they aren't reached by said nested loop.
>> 
>> 
>> With this fix, if we detect that there's a relevant ConstantExpr,
>> we'll look into it as if it were a regular Instruction inside of
>> Bb.getInstList(), which causes us to correctly detect the globals,
>> etc.
> 
> Sounds good.
> 
> Thanks!
> 
> -Hal
> 
>> 
>> 
>> (I included a test case specifically for this -- it's ugly, but we
>> have ~3 nested GEPs with a global at the innermost GEP. It produces
>> the appropriate output)
>> 
>> 
>> George
>> 
>> 
>> On Fri, Jan 30, 2015 at 10:56 AM, Hal Finkel < hfinkel at anl.gov
>
>> wrote:
>> 
>> 
>> ----- Original Message -----
>>> From: "George Burgess IV" < george.burgess.iv at
gmail.com >
>>> To: "Daniel Berlin" < dberlin at dberlin.org >
>>> Cc: "Chandler Carruth" < chandlerc at google.com >,
"Hal Finkel" <
>>> hfinkel at anl.gov >, "Jiangning Liu"
>>> < Jiangning.Liu at arm.com >, "LLVM Developers Mailing
List" <
>>> llvmdev at cs.uiuc.edu >
>>> Sent: Friday, January 30, 2015 8:15:55 AM
>>> Subject: Re: [LLVMdev] question about enabling cfl-aa and
>>> collecting a57 numbers
>>> 
>>> 
>>> 
>>> I'm not exactly thrilled about the size of this diff --
I'll
>>> happily
>>> break it up into more manageable bits later today, because some of
>>> it is test fixes, another bit is a minor bug fix, etc.
>> 
>> Yes, please break it into independent parts.
>> 
>>> 
>>> 
>>> Important bit (WRT ConstantExpr): moved the loop body from
>>> buildGraphFrom into a new function. The body has a few tweaks to
>>> call constexprToEdges on all ConstantExprs that we encounter.
>>> constexprToEdges, naturally, interprets a ConstantExpr (and all
>>> nested ConstantExprs) and places the results into a
>>> SmallVector<Edge>.
>>> 
>>> 
>>> I'm assuming this method of handling ConstantExprs isn't
100%
>>> correct
>>> because I was told that handling them correctly would be more
>>> difficult than I think it is. I can't quite figure out why, so
>>> examples of cases that break my code would be greatly appreciated.
>>> :)
>> 
>> I had thought that the case that Danny had looked at had a constant
>> GEP, and so this constant might alias with other global pointers.
>> How is that handled now?
>> 
>> Thanks again,
>> Hal
>> 
>> 
>> 
>>> 
>>> 
>>> George
>>> 
>>> 
>>> On Mon, Jan 26, 2015 at 2:43 PM, George Burgess IV <
>>> george.burgess.iv at gmail.com > wrote:
>>> 
>>> 
>>> 
>>> 
>>> Inline
>>> 
>>> 
>>> George
>>> 
>>> 
>>> 
>>> 
>>> On Jan 26, 2015, at 1:05 PM, Daniel Berlin < dberlin at
dberlin.org >
>>> wrote:
>>> 
>>> 
>>> George, given that, can you just build constexpr handling (it's
not
>>> as easy as you think) as a separate funciton and have it use it in
>>> the right places?
>>> Will do. :)
>>> 
>>> 
>>> 
>>> 
>>> 
>>> FWIW, my current list of CFLAA issues is:
>>> 
>>> 1. Unknown values (results from ptrtoint, incoming pointers, etc)
>>> are
>>> not treated as unknown. These should be done through graph edge (so
>>> that they can be one way, otherwise, you will unify everything :P)
>>> 
>>> 
>>> 
>>> 
>>> 2. Constexpr handling
>>> 
>>> 
>>> 
>>> 
>>> ^^^ These are correctness issues. I'm pretty sure there are a
few
>>> more but i haven't finished auditing
>>> 3. In a number of places we treat non-pointers as memory-locations
>>> and unify them with pointers. This introduces a lot of spurious
>>> aliasing.
>>> 4. More generally, we induce a lot of spurious aliasing through
>>> things at different dereference levels. In these cases, one may to
>>> the other, but, for example, if we have a foo***, and a foo* (and
>>> neither pointers to unknown things or escapes), the only way for
>>> foo
>>> *** to alias foo* is if there is a graph path with two dereferences
>>> between them.
>>> We seem to get this wrong sometimes. Agreed on all four. Though
>>> naturally it should be fixed, I’d like to see how much of an issue
>>> #4 ends up being when we properly deal with #3.
>>> 
>>> 
>>> 
>>> 
>>> 
>>> 
>>> 
>>> On Sun Jan 25 2015 at 6:44:07 PM Chandler Carruth <
>>> chandlerc at google.com > wrote:
>>> 
>>> 
>>> 
>>> 
>>> 
>>> 
>>> On Sun, Jan 25, 2015 at 6:37 PM, George Burgess IV <
>>> george.burgess.iv at gmail.com > wrote:
>>> 
>>> 
>>>> Fixing that still gives a wrong result, i haven't started
to
>>>> track
>>>> down what *else* is going on here.
>>> 
>>> 
>>> Running with the attached diff + a modified buildGraphFrom to
>>> handle
>>> the constexpr GEPs, we seem to flag everything in test2.ll
>>> (conservatively) correctly.
>>> 
>>> 
>>> Is `store` the only place we can expect to see these constexpr
>>> analogs, or is just about anywhere fair game?
>>> 
>>> 
>>> Any Value can be a ConstantExpr, so all operands to instructions
>>> are
>>> fair game.
>>> 
>>> 
>> 
>> 
>> 
>> --
>> Hal Finkel
>> Assistant Computational Scientist
>> Leadership Computing Facility
>> Argonne National Laboratory
>> 
>> 
> 
> -- 
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150130/0223b868/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cflaa-constexpr-fixes.diff
Type: application/octet-stream
Size: 12067 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150130/0223b868/attachment.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150130/0223b868/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cflaa-danny-changes.diff
Type: application/octet-stream
Size: 4436 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150130/0223b868/attachment-0001.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150130/0223b868/attachment-0002.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cflaa-minor-bugfixes.diff
Type: application/octet-stream
Size: 2203 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150130/0223b868/attachment-0002.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150130/0223b868/attachment-0003.html>