[LLVMdev] question about enabling cfl-aa and collecting a57 numbers

[George Burgess IV]

+Yogesh -- he found bugs (llvm_unreachable reached -- looking into why now)
and said that he'd be interested in helping. Yay!

Status update: Toy implementation of properly handling inttoptr/ptrtoint
conversions (see: the fix for #2 on Danny's list) passes tests. I need to
do a bit of clean up (and want to test it more thoroughly), and will
hopefully have that patch out + a fix for the bug noted above by the end of
the weekend

George

On Wed, Feb 4, 2015 at 12:43 AM, George Burgess IV <
george.burgess.iv at gmail.com> wrote:

> Sounds good, I'll reword that comment. Also, the assert you mentioned
> turned out to be a bad assumption when combined with how I foresee us
> handling inttoptr/ptrtoint in the future, so I'll just replace it with
> slightly more robust code. :)
>
> Thanks for the feedback,
> George
>
> On Tue, Feb 3, 2015 at 11:30 PM, Hal Finkel <hfinkel at anl.gov> wrote:
>
>> Hi George,
>>
>> +// Given an Instruction, this will add it to the graph, along with any
>>
>> +// Instructions that are potentially only available from said Instruction
>>
>> I think this comment is somewhat misleading. You can't really have
>> orphaned instructions: instructions that have been inserted into a basic
>> block must appear in its linked list of instructions that you'll visit when
>> you iterate over all of them. You can have constantexprs, and I think
>> that's what you're try to say.
>>
>> +      assert(Edge.From == Inst.get() &&
>>
>> +          "Expected ConstantExpr edge `From` to evaluate to the
>> ConstantExpr");
>>
>> Indentation is odd here.
>>
>> For algorithmic considerations, I think that Danny is certainly the best
>> person to review these.
>>
>>  -Hal
>>
>> ----- Original Message -----
>> > From: "George Burgess IV" <george.burgess.iv at gmail.com>
>> > To: "Hal J. 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:34:43 PM
>> > Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting
>> a57 numbers
>> >
>> >
>> > 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 >
>> > 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
>> >
>>
>> --
>> 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/20150205/0360704d/attachment.html>