similar to: [LLVMdev] Memory Dependence Analysis

On Jan 14, 2009, at 9:37 AM, David Greene wrote: > Back in August, several of us participated in a discussion about > getting a > more robust memory dependence analysis framework into LLVM. Wojtek > Matyjewicz has done some work on this and he attached a patch to an > e-mail at > the time that built against an older version of LLVM. > > Wojtek, what's the status

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

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

> 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,

> 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 ? I think it is not possible in general, but I believe it is possible in case of affine expressions used as GEP indices. I assume, GEP indices (except indexing into struct) are interpreted as signed integers. It isn't explicitly stated in the LangRef, but

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

Wojtek, If you like, I can help guide this SoC project. I would also like to see if we can coordinate with Alex and Albert, who are doing the class project here. As a first comment, your 3 layers are a good organization but two comments: 1. Layer 1 shd also look at loop bounds and array bounds: those can be used to disprove some deps. 2. The interface will also need to compute direction and

Hi, > Cool! I think the most critical part of this is to get a good > interface for dependence analysis. There are lots of interesting > implementations that have various time/space tradeoffs. > > For example, it would be great if Omega was available as an option, > even if the compiler didn't use it by default. This argues for making > dependence analysis

On Aug 21, 2008, at 1:37 AM, Wojciech Matyjewicz wrote: > 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. We want to model this as an analysis and make following changes. - Rename LoopMemDepAnalysis as DataDependenceAnalysis. Various

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

Hi, Devang Patel wrote: > LLVM loop transformer operates at loop level, which is not what many > optimizers do in general. So, a loop level interface (i.e. based on > LoopPass in llvm) to find loop-carried dependence is preferable to > loop optimizer. Do you mean making Array Dependence Analysis a loop-level analysis? Would its results be available for some function-level pass

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

On Mar 18, 2008, at 9:21 AM, Wojciech Matyjewicz wrote: > Hi, > >> Cool! I think the most critical part of this is to get a good >> interface for dependence analysis. There are lots of interesting >> implementations that have various time/space tradeoffs. >> >> For example, it would be great if Omega was available as an option, >> even if the compiler

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

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

On Monday 19 January 2009 18:21, Dan Gohman wrote: > > Dan, how does the scheduler handle memory dependence? I'm working on > > something that requires memory dependence information for > > MachineInstructions. > > At the moment, it knows simple things, like constant pool loads > don't have dependencies, and references to distinct stack slots are >

On Jan 19, 2009, at 5:06 PM, David Greene wrote: > On Monday 19 January 2009 18:21, Dan Gohman wrote: > >>> Dan, how does the scheduler handle memory dependence? I'm working >>> on >>> something that requires memory dependence information for >>> MachineInstructions. >> >> At the moment, it knows simple things, like constant pool loads

Hi, I have two questions about llvm, and expect your reply very much. 1. Is there any plan of llvm to support Thread-Level Parallelism by using OpenMP, MPI, pthread or llvm-defined directives? If automatic parallelism exploring is very hard, what is the key problem? We can't get the precise data dependence information at compile-time? 2. Can I use the functions provided by llvm to

>> As part of the advanced compilers course semester project (at >> UIUC), we >> are starting to implement array dependence analysis for LLVM. Great! This is something we've needed for a long time. > I'm currently working on a similar project and hoping to finish it in > about two weeks. Cool! I think the most critical part of this is to get a good

Hi, I have a question about the memory dependence analysis. I am trying to use it to selectively enumerate a set of pairs of (load, store) instructions for every function by calling getNonLocalDependency() on the MemoryDependenceAnalysis. This populates a DenseMap<BasicBlock*, Value*>. I just looked up an usage of this in GVN.cpp: MD->getNonLocalDependency(C, deps); for