MemoryDependenceAnalysis Bug or Feature?

Hello,

I’m taking a really good look at the MemoryDependenceAnalysis pass, but I’m slightly confused about one little thing. I think it’s a bug but I’m not confident enough to submit a bug report.

Is there a reason why read-only calls are considered to “clobber” pointers in the non-load case (which is what gets returned due to the fall-through in the switch – see below). It seems this should be returning a “def” instead. My thinking is the code should look like this (from line 288 on, +++ marks addition):

// See if this instruction (e.g. a call or vaarg) mod/ref’s the pointer.
switch (AA->getModRefInfo(Inst, MemPtr, MemSize)) {
case AliasAnalysis::NoModRef:
// If the call has no effect on the queried pointer, just ignore it.
continue;
case AliasAnalysis::Mod:
// If we’re in an invariant region, we can ignore calls that ONLY
// modify the pointer.
if (InvariantTag) continue;
return MemDepResult::getClobber(Inst);
case AliasAnalysis::Ref:
// If the call is known to never store to the pointer, and if this is a
// load query, we can safely ignore it (scan past it).
if (isLoad)
continue;
+++ return MemDepResult::getDef(Inst);
default:
// Otherwise, there is a potential dependence. Return a clobber.
return MemDepResult::getClobber(Inst);
}

If this seems right to you too, I’ve attached the patch. If this isn’t right, can someone please explain the logic?

Thanks,
Marc

MDA.patch (537 Bytes)

Since isLoad == false means we're looking at a store, what this does
is making the store *p depend on the load *p. This is correct -- you
can't move store before load, otherwise load will start returning a
different value.

Eugene

Yes, I’m not arguing that there is a dependence, just that it’s not a clobber dependence. The case of a load is already considered earlier in that function and with isLoad == false it returns MemDepResult::getDef(). My question is: why should a read-only call (which yields AliasAnalysis::Ref and is handled in this code fragment) be any different from e.g. a load. Isn’t a read-only call effectively just a series of loads from a memory-dependence perspective?

In other words, why does this code fragment return MemDepResult::getClobber() instead of MemDepResult::getDef() for a read-only call?

Sorry, I misunderstood the question.
The difference between a load and a read-only call is that load can be
used as the value of the memory location. E.g. DeadStoreElimination
pass removes a store that stores a just loaded value back into the
same location. To do this it checks if the stored value is the value
of load. Read-only call cannot be used like this.
This being said, I don't know if this is the reason for the current
logic, and DSE won't break with your change -- it checks if Def is
indeed a load.

A related question -- it looks like memdep returns Def for store to
load dependence even when they MayAlias. Should it return Clobber for
MayAlias and Def for MustAlias? With the current logic DSE has to
check that SI->getPointerOperand() == DepLoad->getPointerOperand(),
though this is not strictly necessary -- they can be different values
but be MustAlias.

Eugene

Sorry, I misunderstood the question.
The difference between a load and a read-only call is that load can be
used as the value of the memory location. E.g. DeadStoreElimination
pass removes a store that stores a just loaded value back into the
same location. To do this it checks if the stored value is the value
of load. Read-only call cannot be used like this.
This being said, I don’t know if this is the reason for the current
logic, and DSE won’t break with your change – it checks if Def is
indeed a load.

Well as a matter of consistency I think a Def is more appropriate. DSE is just one consumer of memdep analysis, and the analysis I have in mind does not use memdep in the way that DSE or GVN does.

A related question – it looks like memdep returns Def for store to
load dependence even when they MayAlias. Should it return Clobber for
MayAlias and Def for MustAlias? With the current logic DSE has to
check that SI->getPointerOperand() == DepLoad->getPointerOperand(),
though this is not strictly necessary – they can be different values
but be MustAlias.

Personally, I find the Def vs. Clobber distinction rather arbitrary and not very intuitive. A may-alias store “clobbers” but a must-alias store is a “def”? I understand why there is a distinction, but the naming is poor. The comments say the naming is “unusual but pragmatic”, but I have to disagree and say that the information is pragmatic only for a particular set of consumer analyses/transformations, and not across all possible consumers.

As an aside, a newcomer’s understanding is also compromised trying to compress everything into the two bits inside MemDepResult. I understand the desire to meet this constraint, but with three bits you could represent may/must-alias with one bit, ref/mod/invalid/nonlocal with the other two bits and it would be easier to work with.