Flow-Sensitive AA

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
57 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Flow-Sensitive AA

dag-7
I'm not quite understanding how one would use the existing alias analysis
framework to represent a flow-sensitive analysis.

Let's say I have a load and a store and I want to determine whether the load
loads from the same place the store stores to.  Today we'd do something like
this:

AA.alias(load->getPointerOperand(), /* get the size */
        store->getPointerOperand()), /* size *);

There is nothing here that tells AliasAnalyses which program point we're at.

It doesn't seem to be enough to say:

AA.alias(load, /* size */, store, /* size */);

because AliasAnalysis wouldn't know which operands we're interested in.

So does AliasAnalysis need an updated interface, something like:

  virtual AliasResult alias(const Value *V1, unsigned V1Size,
                            const Instruction *V1Inst,
                            const Value *V2, unsigned V2Size,
                            const Instruction *V2Inst);

?  Or am I missing something?

                                                 -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Flow-Sensitive AA

Chris Lattner-2

On Aug 18, 2008, at 3:19 PM, David Greene wrote:

> I'm not quite understanding how one would use the existing alias  
> analysis
> framework to represent a flow-sensitive analysis.

Yep, the current infrastructure isn't set up to support this.

I haven't seen a real world case where flow sensitive AA is useful.  
Normally, the conversion to SSA form is sufficient.  Can you talk  
about cases where this matters to you?

-Chris
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Flow-Sensitive AA

dag-7
On Monday 18 August 2008 17:21, Chris Lattner wrote:
> On Aug 18, 2008, at 3:19 PM, David Greene wrote:
> > I'm not quite understanding how one would use the existing alias
> > analysis
> > framework to represent a flow-sensitive analysis.
>
> Yep, the current infrastructure isn't set up to support this.
>
> I haven't seen a real world case where flow sensitive AA is useful.

Yes, in the general case, flow-sensitive AA isn't worth it.

> Normally, the conversion to SSA form is sufficient.  Can you talk
> about cases where this matters to you?

Mostly it involves tying into our memory dependence analysis which
annotates things on program points.  I need a way to translate back
to our optimizer data structures.

So it's not "flow-sensitive AA" in the strictest sense but it does require
program point information.

I looked at MemoryDependenceAnalysis and it's not quite what I want.
I need to know things like "does this load and store pair interfere," not
"give me the most recent instruction that interferes with this memory
operation."  It's the kinds of things you'd want to ask for scheduling
purposes, where no particular instruction ordering is assumed.

                                         -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Dependence Analysis [was: Flow-Sensitive AA]

dag-7
On Monday 18 August 2008 17:48, David Greene wrote:

> > Normally, the conversion to SSA form is sufficient.  Can you talk
> > about cases where this matters to you?
>
> Mostly it involves tying into our memory dependence analysis which
> annotates things on program points.  I need a way to translate back
> to our optimizer data structures.
>
> So it's not "flow-sensitive AA" in the strictest sense but it does require
> program point information.

Ok, so this is not the ideal way to do things.  AliasAnalysis was just a
convenient way to hook into something.  But as I've gone through this
I've realized it's just not going to work very well.

What I really need is a dependence analysis interface.  I need to know
about loop-carried dependencies and that sort of things, whether two memory
operations reference the same data, distance information, etc..  As far as I
can tell, there's no infrastructure for this in LLVM.

I don't actually need the analysis because we have it in our optimizer.  What
I need is some kind of interface akin to AliasAnalysis that can chain
analyses, etc.

I'm sure there are others working on this.  I believe Vikram mentioned his
group is working on a parallelizing compiler based on LLVM.

I would think it would be straightforward to taken the AliasAnalysis interface
and essentially duplicate it and call it DependenceAnalysis or some such
thing.  But if someone's already done this I'd rather not duplicate the
effort.

                                               -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis [was: Flow-Sensitive AA]

Chris Lattner-2
On Aug 20, 2008, at 8:56 AM, David Greene wrote:
> What I really need is a dependence analysis interface.  I need to know
> about loop-carried dependencies and that sort of things, whether two  
> memory
> operations reference the same data, distance information, etc..  As  
> far as I
> can tell, there's no infrastructure for this in LLVM.

Right, this is something we've wanted for a long time, but noone has  
stepped up to add.

> I don't actually need the analysis because we have it in our  
> optimizer.  What
> I need is some kind of interface akin to AliasAnalysis that can chain
> analyses, etc.

Ok.

> I'm sure there are others working on this.  I believe Vikram  
> mentioned his
> group is working on a parallelizing compiler based on LLVM.

That project is just barely starting to get off the ground and will  
take awhile before it starts doing much, as far as I know.

> I would think it would be straightforward to taken the AliasAnalysis  
> interface
> and essentially duplicate it and call it DependenceAnalysis or some  
> such
> thing.  But if someone's already done this I'd rather not duplicate  
> the
> effort.

In theory, it should be pretty easy to create a new DependenceAnalysis  
analysis class and start piping it around.  It would be nice if there  
was a trivial implementation so that we can write regtests.

-Chris
 
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis [was: Flow-Sensitive AA]

Vikram S. Adve-2
Wojtek Matyjewicz has written a simple DependenceAnalysis interface  
and sent email about it to llvmdev in June -- the message is  
attached.  He said he wrote several tests behind that interface --  
ZIV, strong SIV, Banerjee, and some form of the Delta test -- and two  
students in my Spring class added the Omega test.  I have not reviewed  
his interface yet because I've been traveling almost nonstop since then.

At Illinois, we are working on a parallelizing compiler but we're at  
an extremely early stage.  We too will need a dependence analysis  
interface that can support fairly aggressive analysis, including  
strong tests, direction vectors, perhaps distance vectors, and  
dependence breaking conditions.  We were going to start with Wojtek's  
interface as a strawman.  Collaborations on extending the interface or  
implementation would be very welcome.  I'm copying Matthieu Delahaye  
who is our lead programmer on this effort (he's also on llvmdev).

--Vikram
Associate Professor, Computer Science
University of Illinois at Urbana-Champaign
http://llvm.org/~vadve




On Aug 20, 2008, at 11:27 AM, Chris Lattner wrote:

> On Aug 20, 2008, at 8:56 AM, David Greene wrote:
>> What I really need is a dependence analysis interface.  I need to  
>> know
>> about loop-carried dependencies and that sort of things, whether two
>> memory
>> operations reference the same data, distance information, etc..  As
>> far as I
>> can tell, there's no infrastructure for this in LLVM.
>
> Right, this is something we've wanted for a long time, but noone has
> stepped up to add.
>
>> I don't actually need the analysis because we have it in our
>> optimizer.  What
>> I need is some kind of interface akin to AliasAnalysis that can chain
>> analyses, etc.
>
> Ok.
>
>> I'm sure there are others working on this.  I believe Vikram
>> mentioned his
>> group is working on a parallelizing compiler based on LLVM.
>
> That project is just barely starting to get off the ground and will
> take awhile before it starts doing much, as far as I know.
>
>> I would think it would be straightforward to taken the AliasAnalysis
>> interface
>> and essentially duplicate it and call it DependenceAnalysis or some
>> such
>> thing.  But if someone's already done this I'd rather not duplicate
>> the
>> effort.
>
> In theory, it should be pretty easy to create a new DependenceAnalysis
> analysis class and start piping it around.  It would be nice if there
> was a trivial implementation so that we can write regtests.
>
> -Chris
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Hi all!

I have recently finished the first prototype of data dependence analysis
for LLVM. Now that I have some more time I would like to prepare a
"production" version. In this post I'll try to describe the current
state and propose a work plan.

Currently, the analysis has a very simplified interface (it allows to
query for dependence between two given instructions or whether a given
loop carries any dependence). Also, loop independent dependencies aren't
supported yet. I focused on the main part - an algorithm that checks for
dependence given two instructions. It uses alias analysis info and some
techniques from the Allen & Kennedy book (ZIV test, strong SIV test,
Banerjee test, simpler form of the Delta test). Alexandre X. Duchateau
and Albert Sibelnik added the Omega test based on the Omega library.

I am going to go the Developer Policy's way and work incrementally with
your feedback. What do you think of the following work plan?
 1. Think of possible clients of the analysis and gather their requirements.
 2. Design analysis interface.
 3. Implement the simplest client for testing purposes. (In the
optimistic scenario others starts to implement more clients at this
stage and give better feedback about the interface;) )
 4. Design the analysis internals in a way that make future extensions
(ie. adding different dependence tests) possible.
 5. Implement the analysis and the initial set of dependence tests.

While working on a prototype I gathered some thought on all the above
steps. Also, when I write 'implement' I don't mean starting from scratch
but using the current code as a base.

-Wojtek
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis [was: Flow-Sensitive AA]

dag-7
On Wednesday 20 August 2008 14:07, Vikram S. Adve wrote:

> At Illinois, we are working on a parallelizing compiler but we're at
> an extremely early stage.  We too will need a dependence analysis
> interface that can support fairly aggressive analysis, including
> strong tests, direction vectors, perhaps distance vectors, and
> dependence breaking conditions.  We were going to start with Wojtek's
> interface as a strawman.  Collaborations on extending the interface or
> implementation would be very welcome.  I'm copying Matthieu Delahaye
> who is our lead programmer on this effort (he's also on llvmdev).

Is there some code of the interface we can discuss?  I'm more than happy to
provide input, requirements, etc.  I'll contribute code where I can
(management decision there, but I'm pretty sure I can sell it).

If there's something that's been used for simple things now, let's get it
checked in and start refining it.

                                                     -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis [was: Flow-Sensitive AA]

Vikram S. Adve-2
Wojtek,

Please see David's message below.  Have you or can you check in your  
code, perhaps as a project for now?  That will allow us to start  
looking at it and perhaps collaborating on it.

--Vikram
Associate Professor, Computer Science
University of Illinois at Urbana-Champaign
http://llvm.org/~vadve




On Aug 20, 2008, at 3:05 PM, David Greene wrote:

> On Wednesday 20 August 2008 14:07, Vikram S. Adve wrote:
>
>> At Illinois, we are working on a parallelizing compiler but we're at
>> an extremely early stage.  We too will need a dependence analysis
>> interface that can support fairly aggressive analysis, including
>> strong tests, direction vectors, perhaps distance vectors, and
>> dependence breaking conditions.  We were going to start with Wojtek's
>> interface as a strawman.  Collaborations on extending the interface  
>> or
>> implementation would be very welcome.  I'm copying Matthieu Delahaye
>> who is our lead programmer on this effort (he's also on llvmdev).
>
> Is there some code of the interface we can discuss?  I'm more than  
> happy to
> provide input, requirements, etc.  I'll contribute code where I can
> (management decision there, but I'm pretty sure I can sell it).
>
> If there's something that's been used for simple things now, let's  
> get it
> checked in and start refining it.
>
>                                                     -Dave

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis [was: Flow-Sensitive AA]

Wojciech Matyjewicz
> Wojtek,
>
> Please see David's message below.  Have you or can you check in your  
> code, perhaps as a project for now?  That will allow us to start  
> looking at it and perhaps collaborating on it.

Sure. For now, I am posting it as an attachment, because it does not
build against the current SVN version. It is really basic (for example,
it cannot produce distance vectors, breaking conditions and it does not
handle affine loop bounds), but hope you find some pieces of it useful.

The attached version does not reflect the recent changes in the LLVM IR
(larger set of first-class types) yet, so it should be built against one
of the previous revisions (it works with r50174 for sure). It have to be
configured with --with-llvmsrc and --with-llvmobj switches. Build
process will produce libmemdep.so shared library that can be load into
opt. In the archive, there is also 'test' directory with simple programs
to test the pass. I suggest using such a toolchain:

$ llvm-gcc -c -emit-llvm -O3 <program.c> -o - | opt -load=loopmemdep.so
-loopsimplify -anders-aa -loop-memdep -debug-only=loop-memdep

(Debug output is quite verbose.)

I am investigating what changes are necessary to add support for
first-class structs and arrays and will prepare a version to check in as
a LLVM project if there still is interest.

Wojtek

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

loopmemdep.tar.bz2 (49K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis [was: Flow-Sensitive AA]

Vikram S. Adve-2
Great, thanks!  How much work do you think it will take to bring it up  
to date with the LLVM IR, except *ignoring* first-class structs and  
arrays for now?  I believe llvm-gcc does not generate those in most  
cases and we can do a lot without supporting those.  What else is  
missing relative to the current LLVM IR?

Thanks,

--Vikram
Associate Professor, Computer Science
University of Illinois at Urbana-Champaign
http://llvm.org/~vadve




On Aug 21, 2008, at 3:37 AM, Wojciech Matyjewicz wrote:

>> Wojtek,
>>
>> Please see David's message below.  Have you or can you check in your
>> code, perhaps as a project for now?  That will allow us to start
>> looking at it and perhaps collaborating on it.
>
> Sure. For now, I am posting it as an attachment, because it does not
> build against the current SVN version. It is really basic (for  
> example,
> it cannot produce distance vectors, breaking conditions and it does  
> not
> handle affine loop bounds), but hope you find some pieces of it  
> useful.
>
> The attached version does not reflect the recent changes in the LLVM  
> IR
> (larger set of first-class types) yet, so it should be built against  
> one
> of the previous revisions (it works with r50174 for sure). It have  
> to be
> configured with --with-llvmsrc and --with-llvmobj switches. Build
> process will produce libmemdep.so shared library that can be load into
> opt. In the archive, there is also 'test' directory with simple  
> programs
> to test the pass. I suggest using such a toolchain:
>
> $ llvm-gcc -c -emit-llvm -O3 <program.c> -o - | opt -
> load=loopmemdep.so
> -loopsimplify -anders-aa -loop-memdep -debug-only=loop-memdep
>
> (Debug output is quite verbose.)
>
> I am investigating what changes are necessary to add support for
> first-class structs and arrays and will prepare a version to check  
> in as
> a LLVM project if there still is interest.
>
> Wojtek
> <loopmemdep.tar.bz2>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis [was: Flow-Sensitive AA]

Chris Lattner-2

On Aug 21, 2008, at 7:35 AM, Vikram S. Adve wrote:

> Great, thanks!  How much work do you think it will take to bring it up
> to date with the LLVM IR, except *ignoring* first-class structs and
> arrays for now?  I believe llvm-gcc does not generate those in most
> cases and we can do a lot without supporting those.

Right, the design of the first class aggregates is that optimizers  
should generally assume they don't exist.  This is the same sort of  
thing as how most optimizers assume that mem2reg has been run.  Of  
course, this should only affect effectiveness, not correctness.

-Chris
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis [was: Flow-Sensitive AA]

Wojciech Matyjewicz
In reply to this post by Vikram S. Adve-2
> Great, thanks!  How much work do you think it will take to bring it up
> to date with the LLVM IR, except *ignoring* first-class structs and
> arrays for now?  I believe llvm-gcc does not generate those in most
> cases and we can do a lot without supporting those.  What else is
> missing relative to the current LLVM IR?

To my surprise, it took almost no time (only some minor changes
unrelated to the IR were necessary). Furthermore, it seems that lack of
support for first-class structs and arrays is not a matter of
correctness but a matter of precision. I think the analysis should give
correct answers even for bitcode that uses recently introduced
instructions. I have attached a version that can be built against the
SVN version.

The code contains many FIXME notes. In general, they indicate
possibilities of efficiency or precision improvements rather than bugs.
However, there is one issue I have ignored - possibility of overflow in
the index expression. Suppose, we have such a loop:
  for (i8 i = 0; i != 200; ++i) {
    A[2 * i + 5] = ...
    ... = A[2 * i + 3]
  }
If both index expressions are evaluated in 8-bit arithmetic,
then the dependence equation should be solved in modular arithmetic:
  2 * i + 5 == 2 * (i + delta) + 3 (mod 256)
So the dependence distance is delta == 1 or delta == -127 what gives
two direction vectors: (<), (>). My version will produce only the first
one. Taking into account overflow issue during dependence analysis seems
very difficult to me. Does anybody have some experience in this area?
Fortunately, programmers generally do not write programs in such a
nasty way.

And now a small explaination of debug output for mandel.c (included in
the attachment):

   [ ... ]

   Testing DMA dependence between:
        DMA to %tmp95 of size 1 (m)
        DMA to %tmp95 of size 1 (m)
// Testing for output dependence between pict[py * pict_width + px]
// assignments in different iterations. DMA stands for Direct Memory
// Access that means an LLVM instruction that directly accesses memory
// (the opposite is call site).

   [ ... ]

      CommonNestSize: 2
// Number of loops that are common for both instructions
// (In this example the first and second instructions are the same -
// we are testing for self-dependence)

      LBounds1: (1049, 1679)
// Bounds for all loops containing the first instruction

      LBounds2: (1049, 1679)
// Bounds for all loop containing the second instruction

      ALengths: (0)
// Dimensions of accessed array, 0 = unknown

      Indices1: (1680*i_0 + 1*i_1 + 0)
// Affine formula for index expression in the first instruction
// i_0 means induction variable for loop at level 0 (outermost),
// i_1 means IV for loop at level 1, etc...

      Indices2: (1680*i_0 + 1*i_1 + 0)
// Affine formula for index expression in the first instruction

       Group: (0)
        Pos 0:
         Banerjee test:
          U1: (1049, 1679); U2: (1049, 1679)
          A1: (1680, 1), B1: 0
          A2: (1680, 1), B2: 0
           Trying (*,*): (L = -1763999, M = 0, R = 1763999)1
           Trying (<,*): (L = -1763999, M = 0, R = -1)0
           Trying (=,*): (L = -1679, M = 0, R = 1679)1
           Trying (=,<): (L = -1679, M = 0, R = -1)0
           Trying (=,=): (L = 0, M = 0, R = 0)1
           Trying (=,>): (L = 1, M = 0, R = 1679)0
           Trying (>,*): (L = 1, M = 0, R = 1763999)0
         possible dependence; direction vectors : { (=,=) }
        Delta test: possible dependence; direction vectors : { (=,=) }
// Dependence tester internals

    Array dependence tester: dependence; direction vectors: { (=,=) }
// The answer.

-Wojtek

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

loopmemdep.tar.bz2 (52K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis [was: Flow-Sensitive AA]

Matthieu Delahaye
In reply to this post by dag-7



>However, there is one issue I have ignored - possibility of overflow in
>the index expression. Suppose, we have such a loop:
>  for (i8 i = 0; i != 200; ++i) {
>    A[2 * i + 5] = ...
>    ... = A[2 * i + 3]
>  }
>If both index expressions are evaluated in 8-bit arithmetic,
>then the dependence equation should be solved in modular arithmetic:
>  2 * i + 5 == 2 * (i + delta) + 3 (mod 256)
>So the dependence distance is delta == 1 or delta == -127 what gives
>two direction vectors: (<), (>). My version will produce only the first
>one. Taking into account overflow issue during dependence analysis seems
>very difficult to me. Does anybody have some experience in this area?
>Fortunately, programmers generally do not write programs in such a
>nasty way.

I asked myself the same question. Without mod, how do you ensure that for instance the expression 2*i+255 was not actually 2*i-1 ?


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis [was: Flow-Sensitive AA]

Vikram S. Adve-2
In the general case, I think you have to be conservative about this  
because programmers may deliberately want this kind of "wraparound"  
behavior, e.g., with periodic boundary conditions.  But 99.9% of  
programs probably don't need that so it would be bad to penalize them  
for this corner case.  In such a situation, I think you just have to  
support both choices, but choose the default as sensibly as possible.  
I discussed this with Matthieu and this is what we came up with:

1. (Eventually) Support both choices: conservative or optimistic.  
Conservative means you assume that index arithmetic can wrap around;  
optimistic assumes it cannot.  What I think you've implemented is the  
optimistic case.

2. Have a default choice but give the programmer an option to force  
this on or off.

3. (Matthieu's idea) Default to optimistic if the index expressions  
are i32, but conservative if i8 or i16.  This assumes that there is no  
good reason to use i8 or i16 index variables except for wraparound  
behavior (and it is highly unlikely that programmers are using arrays  
of size 2^32 *and* requiring wraparound behavior for that).

Of course, for now, we don't have to implement the conservative  
version: what you've done should be good enough.

--Vikram
Associate Professor, Computer Science
University of Illinois at Urbana-Champaign
http://llvm.org/~vadve




On Aug 22, 2008, at 9:41 AM, [hidden email] wrote:

>
>
>
>> However, there is one issue I have ignored - possibility of  
>> overflow in
>> the index expression. Suppose, we have such a loop:
>> for (i8 i = 0; i != 200; ++i) {
>>   A[2 * i + 5] = ...
>>   ... = A[2 * i + 3]
>> }
>> If both index expressions are evaluated in 8-bit arithmetic,
>> then the dependence equation should be solved in modular arithmetic:
>> 2 * i + 5 == 2 * (i + delta) + 3 (mod 256)
>> So the dependence distance is delta == 1 or delta == -127 what gives
>> two direction vectors: (<), (>). My version will produce only the  
>> first
>> one. Taking into account overflow issue during dependence analysis  
>> seems
>> very difficult to me. Does anybody have some experience in this area?
>> Fortunately, programmers generally do not write programs in such a
>> nasty way.
>
> I asked myself the same question. Without mod, how do you ensure  
> that for instance the expression 2*i+255 was not actually 2*i-1 ?
>
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis [was: Flow-Sensitive AA]

Chris Lattner-2

On Aug 22, 2008, at 9:30 AM, Vikram S. Adve wrote:

> In the general case, I think you have to be conservative about this
> because programmers may deliberately want this kind of "wraparound"
> behavior, e.g., with periodic boundary conditions.  But 99.9% of
> programs probably don't need that so it would be bad to penalize them
> for this corner case.  In such a situation, I think you just have to
> support both choices, but choose the default as sensibly as possible.
> I discussed this with Matthieu and this is what we came up with:

C has a way to express this: signed integers are defined to never  
overflow, unsigned integers are defined to wrap gracefully on  
overflow.  Other languages that target this may want some sort of  
command line option to control the behavior or the language may define  
it one way or the other.

We don't model this in LLVM IR, but this is a desired feature if  
anyone is interested.  Capturing this in the IR is a better way to go  
than having the optimizers have a big global knob.

-Chris

>
>
> 1. (Eventually) Support both choices: conservative or optimistic.
> Conservative means you assume that index arithmetic can wrap around;
> optimistic assumes it cannot.  What I think you've implemented is the
> optimistic case.
>
> 2. Have a default choice but give the programmer an option to force
> this on or off.
>
> 3. (Matthieu's idea) Default to optimistic if the index expressions
> are i32, but conservative if i8 or i16.  This assumes that there is no
> good reason to use i8 or i16 index variables except for wraparound
> behavior (and it is highly unlikely that programmers are using arrays
> of size 2^32 *and* requiring wraparound behavior for that).
>
> Of course, for now, we don't have to implement the conservative
> version: what you've done should be good enough.
>
> --Vikram
> Associate Professor, Computer Science
> University of Illinois at Urbana-Champaign
> http://llvm.org/~vadve
>
>
>
>
> On Aug 22, 2008, at 9:41 AM, [hidden email] wrote:
>
>>
>>
>>
>>> However, there is one issue I have ignored - possibility of
>>> overflow in
>>> the index expression. Suppose, we have such a loop:
>>> for (i8 i = 0; i != 200; ++i) {
>>>  A[2 * i + 5] = ...
>>>  ... = A[2 * i + 3]
>>> }
>>> If both index expressions are evaluated in 8-bit arithmetic,
>>> then the dependence equation should be solved in modular arithmetic:
>>> 2 * i + 5 == 2 * (i + delta) + 3 (mod 256)
>>> So the dependence distance is delta == 1 or delta == -127 what gives
>>> two direction vectors: (<), (>). My version will produce only the
>>> first
>>> one. Taking into account overflow issue during dependence analysis
>>> seems
>>> very difficult to me. Does anybody have some experience in this  
>>> area?
>>> Fortunately, programmers generally do not write programs in such a
>>> nasty way.
>>
>> I asked myself the same question. Without mod, how do you ensure
>> that for instance the expression 2*i+255 was not actually 2*i-1 ?
>>
>>
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis [was: Flow-Sensitive AA]

Dale Johannesen

On Aug 22, 2008, at 9:34 AMPDT, Chris Lattner wrote:

>
> On Aug 22, 2008, at 9:30 AM, Vikram S. Adve wrote:
>
>> In the general case, I think you have to be conservative about this
>> because programmers may deliberately want this kind of "wraparound"
>> behavior, e.g., with periodic boundary conditions.  But 99.9% of
>> programs probably don't need that so it would be bad to penalize them
>> for this corner case.  In such a situation, I think you just have to
>> support both choices, but choose the default as sensibly as possible.
>> I discussed this with Matthieu and this is what we came up with:
>
> C has a way to express this: signed integers are defined to never
> overflow,

More precisely, signed integer overflow is undefined behavior, which  
gives the compiler great latitude.
Assuming this will never happen and doing optimizations on that basis  
is valid, but so are other things.
An easy implementation, which often matches user expectations because  
it is what most hardware does,
is to treat signed and unsigned overflow alike, with clean wraparound.

> unsigned integers are defined to wrap gracefully on
> overflow.  Other languages that target this may want some sort of
> command line option to control the behavior or the language may define
> it one way or the other.
>
> We don't model this in LLVM IR, but this is a desired feature if
> anyone is interested.  Capturing this in the IR is a better way to go
> than having the optimizers have a big global knob.
>
> -Chris
>
>>
>>
>> 1. (Eventually) Support both choices: conservative or optimistic.
>> Conservative means you assume that index arithmetic can wrap around;
>> optimistic assumes it cannot.  What I think you've implemented is the
>> optimistic case.
>>
>> 2. Have a default choice but give the programmer an option to force
>> this on or off.
>>
>> 3. (Matthieu's idea) Default to optimistic if the index expressions
>> are i32, but conservative if i8 or i16.  This assumes that there is  
>> no
>> good reason to use i8 or i16 index variables except for wraparound
>> behavior (and it is highly unlikely that programmers are using arrays
>> of size 2^32 *and* requiring wraparound behavior for that).
>>
>> Of course, for now, we don't have to implement the conservative
>> version: what you've done should be good enough.
>>
>> --Vikram
>> Associate Professor, Computer Science
>> University of Illinois at Urbana-Champaign
>> http://llvm.org/~vadve
>>
>>
>>
>>
>> On Aug 22, 2008, at 9:41 AM, [hidden email] wrote:
>>
>>>
>>>
>>>
>>>> However, there is one issue I have ignored - possibility of
>>>> overflow in
>>>> the index expression. Suppose, we have such a loop:
>>>> for (i8 i = 0; i != 200; ++i) {
>>>> A[2 * i + 5] = ...
>>>> ... = A[2 * i + 3]
>>>> }
>>>> If both index expressions are evaluated in 8-bit arithmetic,
>>>> then the dependence equation should be solved in modular  
>>>> arithmetic:
>>>> 2 * i + 5 == 2 * (i + delta) + 3 (mod 256)
>>>> So the dependence distance is delta == 1 or delta == -127 what  
>>>> gives
>>>> two direction vectors: (<), (>). My version will produce only the
>>>> first
>>>> one. Taking into account overflow issue during dependence analysis
>>>> seems
>>>> very difficult to me. Does anybody have some experience in this
>>>> area?
>>>> Fortunately, programmers generally do not write programs in such a
>>>> nasty way.
>>>
>>> I asked myself the same question. Without mod, how do you ensure
>>> that for instance the expression 2*i+255 was not actually 2*i-1 ?
>>>
>>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> [hidden email]         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis [was: Flow-Sensitive AA]

Vikram S. Adve-2
On Aug 22, 2008, at 11:53 AM, Dale Johannesen wrote:

>
> On Aug 22, 2008, at 9:34 AMPDT, Chris Lattner wrote:
>
>>
>> On Aug 22, 2008, at 9:30 AM, Vikram S. Adve wrote:
>>
>>> In the general case, I think you have to be conservative about this
>>> because programmers may deliberately want this kind of "wraparound"
>>> behavior, e.g., with periodic boundary conditions.  But 99.9% of
>>> programs probably don't need that so it would be bad to penalize  
>>> them
>>> for this corner case.  In such a situation, I think you just have to
>>> support both choices, but choose the default as sensibly as  
>>> possible.
>>> I discussed this with Matthieu and this is what we came up with:
>>
>> C has a way to express this: signed integers are defined to never
>> overflow,

Ok, I thought they both had the same wraparound behavior: thanks for  
clarifying that.



>> More precisely, signed integer overflow is undefined behavior, which
> gives the compiler great latitude.
> Assuming this will never happen and doing optimizations on that basis
> is valid, but so are other things.
> An easy implementation, which often matches user expectations because
> it is what most hardware does,
> is to treat signed and unsigned overflow alike, with clean wraparound.


That makes sense.  But we would have to distinguish them during  
dependence analysis at least, if we want to use the solution Chris  
suggested.  Which brings me to a question:


>> unsigned integers are defined to wrap gracefully on
>> overflow.  Other languages that target this may want some sort of
>> command line option to control the behavior or the language may  
>> define
>> it one way or the other.
>>
>> We don't model this in LLVM IR, but this is a desired feature if
>> anyone is interested.  Capturing this in the IR is a better way to go
>> than having the optimizers have a big global knob.


But signed and unsigned values are not distinguished any more in the  
LLVM IR, and I don't think you're suggesting we restore unsigned  
types.  What do you have in mind here?

--Vikram

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis [was: Flow-Sensitive AA]

Devang Patel
In reply to this post by Wojciech Matyjewicz
Hi Wojtek,

This is a great start. I'll focus and try to understand your interface  
design and choices. Here are my initial thoughts based on a quick read.

The only interface provided by LoopMemDepAnalysis is "bool  
carriesDependence()" which may not be sufficient. But we can extend  
this.

The ArrayDepTest provides testDependenc() as well as testPositions().  
I'm not very clear about the testPositions(). Would it be possible for  
you to explain this ?

One nit-pick, I see that some of the interfaces use tons of parameter,  
which is something I'd like reduce for ease of use.

Thanks for posting your work.
-
Devang
On Aug 21, 2008, at 1:37 AM, Wojciech Matyjewicz wrote:

>> Wojtek,
>>
>> Please see David's message below.  Have you or can you check in your
>> code, perhaps as a project for now?  That will allow us to start
>> looking at it and perhaps collaborating on it.
>
> Sure. For now, I am posting it as an attachment, because it does not
> build against the current SVN version. It is really basic (for  
> example,
> it cannot produce distance vectors, breaking conditions and it does  
> not
> handle affine loop bounds), but hope you find some pieces of it  
> useful.
>
> The attached version does not reflect the recent changes in the LLVM  
> IR
> (larger set of first-class types) yet, so it should be built against  
> one
> of the previous revisions (it works with r50174 for sure). It have  
> to be
> configured with --with-llvmsrc and --with-llvmobj switches. Build
> process will produce libmemdep.so shared library that can be load into
> opt. In the archive, there is also 'test' directory with simple  
> programs
> to test the pass. I suggest using such a toolchain:
>
> $ llvm-gcc -c -emit-llvm -O3 <program.c> -o - | opt -
> load=loopmemdep.so
> -loopsimplify -anders-aa -loop-memdep -debug-only=loop-memdep
>
> (Debug output is quite verbose.)
>
> I am investigating what changes are necessary to add support for
> first-class structs and arrays and will prepare a version to check  
> in as
> a LLVM project if there still is interest.
>
> Wojtek
> <loopmemdep.tar.bz2>_______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis [was: Flow-Sensitive AA]

Mike Stump
In reply to this post by Chris Lattner-2
On Aug 22, 2008, at 9:34 AM, Chris Lattner wrote:
> C has a way to express this: signed integers are defined to never
> overflow, unsigned integers are defined to wrap gracefully on
> overflow.

And gcc has yet more fun in it:

        -fstrict-overflow
            Allow the compiler to assume strict signed overflow rules,  
depending on the language
            being compiled.  For C (and C++) this means that overflow  
when doing arithmetic with
            signed numbers is undefined, which means that the compiler  
may assume that it will
            not happen.  This permits various optimizations.  For  
example, the compiler will
            assume that an expression like "i + 10 > i" will always be  
true for signed "i".  This
            assumption is only valid if signed overflow is undefined,  
as the expression is false
            if "i + 10" overflows when using twos complement  
arithmetic.  When this option is in
            effect any attempt to determine whether an operation on  
signed numbers will overflow
            must be written carefully to not actually involve overflow.

            See also the -fwrapv option.  Using -fwrapv means that  
signed overflow is fully
            defined: it wraps.  When -fwrapv is used, there is no  
difference between
            -fstrict-overflow and -fno-strict-overflow.  With -fwrapv  
certain types of overflow
            are permitted.  For example, if the compiler gets an  
overflow when doing arithmetic
            on constants, the overflowed value can still be used with -
fwrapv, but not otherwise.

            The -fstrict-overflow option is enabled at levels -O2, -
O3, -Os.

        -ftrapv
            This option generates traps for signed overflow on  
addition, subtraction,
            multiplication operations.

        -fwrapv
            This option instructs the compiler to assume that signed  
arithmetic overflow of
            addition, subtraction and multiplication wraps around  
using twos-complement
            representation.  This flag enables some optimizations and  
disables others.  This
            option is enabled by default for the Java front-end, as  
required by the Java language
            specification.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Dependence Analysis [was: Flow-Sensitive AA]

Vikram S. Adve-2
Thanks!  This is all very interesting, and tells me that LLVM has a  
way to go to fully support all of these capabilities (if that is the  
right thing to do, which isn't clear).  OTOH, it looks like a lot of  
real-world software that is using LLVM already doesn't seem to be  
affected by the lack of them.

Does anyone know of any C/C++ programs that require integer overflow  
on signed arithmetic (even though it is not strictly allowed by the  
standard)?

Also, does anyone know how -ftrapv is implemented on processors that  
don't have hardware detection of integer overflow?  It sounds very  
expensive to do entirely in software.

Thanks,

--Vikram
Associate Professor, Computer Science
University of Illinois at Urbana-Champaign
http://llvm.org/~vadve




On Aug 22, 2008, at 3:50 PM, Mike Stump wrote:

> On Aug 22, 2008, at 9:34 AM, Chris Lattner wrote:
>> C has a way to express this: signed integers are defined to never
>> overflow, unsigned integers are defined to wrap gracefully on
>> overflow.
>
> And gcc has yet more fun in it:
>
>        -fstrict-overflow
>            Allow the compiler to assume strict signed overflow rules,
> depending on the language
>            being compiled.  For C (and C++) this means that overflow
> when doing arithmetic with
>            signed numbers is undefined, which means that the compiler
> may assume that it will
>            not happen.  This permits various optimizations.  For
> example, the compiler will
>            assume that an expression like "i + 10 > i" will always be
> true for signed "i".  This
>            assumption is only valid if signed overflow is undefined,
> as the expression is false
>            if "i + 10" overflows when using twos complement
> arithmetic.  When this option is in
>            effect any attempt to determine whether an operation on
> signed numbers will overflow
>            must be written carefully to not actually involve overflow.
>
>            See also the -fwrapv option.  Using -fwrapv means that
> signed overflow is fully
>            defined: it wraps.  When -fwrapv is used, there is no
> difference between
>            -fstrict-overflow and -fno-strict-overflow.  With -fwrapv
> certain types of overflow
>            are permitted.  For example, if the compiler gets an
> overflow when doing arithmetic
>            on constants, the overflowed value can still be used with -
> fwrapv, but not otherwise.
>
>            The -fstrict-overflow option is enabled at levels -O2, -
> O3, -Os.
>
>        -ftrapv
>            This option generates traps for signed overflow on
> addition, subtraction,
>            multiplication operations.
>
>        -fwrapv
>            This option instructs the compiler to assume that signed
> arithmetic overflow of
>            addition, subtraction and multiplication wraps around
> using twos-complement
>            representation.  This flag enables some optimizations and
> disables others.  This
>            option is enabled by default for the Java front-end, as
> required by the Java language
>            specification.
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
123