Memory Dependence Analysis

Project Infrastructure LLVM Dev List Archives
1

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 of this patch? Does it build against HEAD? Do you
plan to check it in any time soon?

I've just run into a couple of situations where I need memory dependence
information. The memory dependence analysis in llvm 2.3 provides very
conservative information but it would be nice to have something better.

We're in the middle of upgrading to 2.4 here and I see that
MemoryDependenceAnalysis has changed a bit. What are the major changes here?

There are a couple of additional requirements I've run into over the last few
days:

1. I need something that can operate on MachineInstructions. Currently
nothing in LLVM supports this. One of the places I want memory dependence
analaysis is in the spiller to eliminate useless spills and reloads.

2. I need something that understands false sharing. That is, optionally the
memory dependence analysis should return dependencies that might not be exact
aliases in memory but that might touch the same cache line. This is important
for efficient parallelization among other things.

Any thoughts on either of these requirements?

I'm going to see if I can convince management to let me devote some time to
this. It may be the case that they want me to interface to our existing
memory dependence information in our optimizer. While we want to be able to
do that, I also want to improve LLVM's native analysis.

                                         -Dave

2

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 of this patch? Does it build against HEAD? Do you
plan to check it in any time soon?

No idea here :wink:

We're in the middle of upgrading to 2.4 here and I see that
MemoryDependenceAnalysis has changed a bit. What are the major changes here?

MemoryDependenceAnalysis does *memory* def/use analysis (what store does a load depend on), but does not do *loop dependence* analysis. I assume you're interested in the dependence analysis, not really just def/use of memory.

-Chris

3

> Wojtek, what's the status of this patch? Does it build against
> HEAD? Do you
> plan to check it in any time soon?

No idea here :wink:

Sure. :slight_smile:

IIRC Wojtek is working on loop dependence, which of course is different
from memory def/use information as you note below. Sorry for mixing up terms.

> We're in the middle of upgrading to 2.4 here and I see that
> MemoryDependenceAnalysis has changed a bit. What are the major
> changes here?

MemoryDependenceAnalysis does *memory* def/use analysis (what store
does a load depend on), but does not do *loop dependence* analysis. I
assume you're interested in the dependence analysis, not really just
def/use of memory.

Eventually we want both. In the near-term, I just need memory dependence.
We're doing multiple different things and thus need different analyses.

                                            -Dave