Meaning of "clobbers" in LLVM

Beginners
1

Hello. First of all excuse any possible “naiveness” of the question; i am new to llvm and self-taught in compilers/program-analysis etc.
So i am a little bit confused what the term “clobbers” means, especially in the context of memory analyses. For instance, i am not sure how to interpret the following from the MemorySSA docs :

The operands of a given MemoryAccess are all (potential) clobbers of said MemoryAccess, and the value produced by a MemoryAccess can act as a clobber for other MemoryAccesses…

I also asked this question on SO a while ago but got no answers: compiler construction - What does "clobbers" mean in the context of LLVM's memory dependence analysis - Stack Overflow

Thanks in advance

2

I think in this context it is used to refer to ‘overwriting memory’.

For MemorySSA concretely that means that traversing the operands of a MemoryAccess provides a way to access all memory accesses that may (partly) overwrite the memory accessed by the given MemoryAccess.

3

Clobber refers to an access (or instruction) overwriting some part of the memory that another access (or instruction) is either reading from or writing to.
The terminology for “clobber” is used similar to that of the synonym “thrash”, when saying “the cache is being thrashed”; both refer to overwriting memory.

Let’s use the example from the documentation:

define void @foo() {
entry:
  %p1 = alloca i8
  %p2 = alloca i8
  %p3 = alloca i8
  ; 1 = MemoryDef(liveOnEntry)
  store i8 0, i8* %p3
  br label %while.cond

while.cond:
  ; 6 = MemoryPhi({%0,1},{if.end,4})
  br i1 undef, label %if.then, label %if.else

if.then:
  ; 2 = MemoryDef(6)
  store i8 0, i8* %p1
  br label %if.end

if.else:
  ; 3 = MemoryDef(6)
  store i8 1, i8* %p2
  br label %if.end

if.end:
  ; 5 = MemoryPhi({if.then,2},{if.else,3})
  ; MemoryUse(5)
  %1 = load i8, i8* %p1
  ; 4 = MemoryDef(5)
  store i8 2, i8* %p2
  ; MemoryUse(1)
  %2 = load i8, i8* %p3
  br label %while.cond
}

In MemorySSA when we look for the clobbering access, this translates to “look up the IR and find the next MemoryAccess that can write to the same memory that I am reading from or writing to.”

For the first access: “; 1 = MemoryDef(liveOnEntry)”, its operand is liveOnEntry. So “1”'s clobbering access is “liveOnEntry”. The “liveOnEntry” is just a marker referring to whatever value existed at that memory location.

The access inside the loop: “2 = MemoryDef(6)” says its location may be clobbered by “; 6 = MemoryPhi(…)”. This means that the memory location modified by the store instruction “store i8 0, i8* %p1” may have been modified by an access in the phi’s access list: “; 6 = MemoryPhi({%0,1},{if.end,4})”. This could be either the MemoryDef outside the loop (1), or the MemoryDef inside the loop (4).

The access: “; MemoryUse(5)” is a read only. It’s clobbering access (i.e. the access that writes the memory that’s being read at this point, can be found by looking at access “; 5 = MemoryPhi({if.then,2},{if.else,3})”.

This kind of information helps in program analysis. For example, if the code was updated such that we have “2 = MemoryDef(liveOnEntry)” inside the loop, when looking for the clobbering access we will notice there is no access inside the loop that writes to the same memory location.

I hope this helps.

4

Thank you very much. This was actually very helpful. I have a couple of follow up questions if you don’t mind, specific to MemorySSA:

Is a clobbering access equivalent to a reaching def for the src of a MemoryUse and the tgt of a MemoryDef? Also, if i understand this right, a MemoryPhi’s operands are always MemoryDefs and never MemoryUses, right?

if the code was updated such that we have “2 = MemoryDef(liveOnEntry)” inside the loop, when looking for the clobbering access we will notice there is no access inside the loop that writes to the same memory location.

Is this not the case with 2 = MemoryDef(1) because 1 may be a clobber due to 6 = MemoryPhi({%0,1},{if.end,4}) ?

Finally, does it follow that the value read here %2 = load i8, i8* %p3 is never modified in the loop? If so, is it because the clobbering access (1) is before the loop?

5

The short answer is yes.
A longer answer involves two more implementation details: optimized accesses and optimizing past MemoryPhis.
Assume for this argument, all MemoryUses are optimized (like you noticed the 2 = MemoryDef(1) doesn’t point to the 6 = MemoryPhi). MemoryDefs do not start off optimized, and even when they are, a “defining” access is also kept around. The “defining” access is the MemoryDef immediately above it, which can be viewed as a very conservative reaching definition. The optimized access is closer to an actual reaching definition, but it’s limited by having a single MemoryPhi in each block. If the optimizing walk cannot optimize past a MemoryPhi, then the MemoryPhi is the optimized access; it’s not creating a list of reaching definitions, one for each incoming block, even if it could optimize more on a particular path. The same is true for MemoryUses when it comes to optimize past a MemoryPhi.

Yes.

Yes and yes.
This is an example of a load that can be hoisted outside the loop.

Happy to help!

6

I see. Thanks again :slight_smile:

7

Let me clarify this, as some folks found it confusing and I should have elaborated more.

If the example I gave had 2 = MemoryDef(1) instead of 2 = MemoryDef(liveOnEntry), the same thing would apply. Since 1 = MemoryDef is outside the loop, there are no accesses inside the loop that may write to the same memory location.

The value loaded at %2 = load i8, i8* %p3 is a candidate for hoisting because its clobbering access is outside the loop.
In practice, there are additional checks that are made to ensure that hoisting is legal. So this check is necessary, but it may not be sufficient.