Understanding Chains

Hi,

I am working on writing a backend in LLVM and I am having a little trouble completely understanding chains. As far as I can tell, chains are used to represent dependencies that can’t be expressed by the typical def-use dependency. But I am uncertain where and how I should be using chains.

In the Code Generator documentation, they describe that chains should be used with instructions that have side effects loads, stores, calls, etc. I guess I am confused to as why those instructions need chains. For example, won’t loads have a dependency on address to ensure they are only scheduled after address generation. And stores will have dependencies and addresses and results to ensure they only occur after those values are created. Is it because of memory disambiguation causing us to be conservative and needing to ensure that certain store/loads aren’t re-ordered respect to each other?

I guess the real question is when I include chains for operations and when I want to return chains from operations (especially intrinsics). For example, with the backend, when I am inserting Loads from the stacks, I don’t want to chain them all together for performance, right, since it doesn’t matter when the loads are scheduled (as long as it is before the use). But I should chain them to the incoming chain from LowerFormalArguments parameter.

On somewhat related note, take this example DAG https://i.stack.imgur.com/RQRpq.gif, why does copyfromreg need a chain input?

Thanks
-Dilan

Hi Dilan,

In the Code Generator documentation, they describe that chains should be
used with instructions that have side effects loads, stores, calls, etc. I
guess I am confused to as why those instructions need chains. For example,
won't loads have a dependency on address to ensure they are only scheduled
after address generation.

The address calculation will be ordered, but the memory being accessed
isn't modelled in the DAG. So without chains LLVM won't know which of
a load and a store to the same address needs to happen first.

Is it
because of memory disambiguation causing us to be conservative and needing
to ensure that certain store/loads aren't re-ordered respect to each other?

Sort of, the problem exists even if we know for sure that two
operations are to the same address though, so I wouldn't call it
"conservative" really, we simply have no way to decide without Chains.

I guess the real question is when I include chains for operations and when I
want to return chains from operations (especially intrinsics). For example,
with the backend, when I am inserting Loads from the stacks, I don't want
to chain them all together for performance, right, since it doesn't matter
when the loads are scheduled (as long as it is before the use). But I should
chain them to the incoming chain from LowerFormalArguments parameter.

For FormalArguments that should be OK because you generally know for a
fact that they're to different addresses so reordering them is
harmless.

On somewhat related note, take this example DAG
https://i.stack.imgur.com/RQRpq.gif, why does copyfromreg need a chain
input?

It's a very similar issue. The physical registers aren't values in the
DAG so if your DAG contained a CopyFromReg and a CopyToReg mentioning
the same register LLVM has no way of knowing which it should do first,
but that has important effects on the result.

As with loads, LowerFormalArguments should be able to use the entry
node for the chain.

You can sort of think of physical registers as just another kind of
memory to unify the model.

Cheers.

Tim.

I am working on writing a backend in LLVM and I am having a little trouble completely understanding chains. As far as I can tell, chains are used to represent dependencies that can't be expressed by the typical def-use dependency. But I am uncertain where and how I should be using chains.

The edges in the selection DAG generally represent def/use relationship, that is, a producer of a value will have an edge connecting it to a user of that value. Dependencies based on side-effects are not representable that way, because the side-effects are not represented as values. For example, a store to a memory location has a side effect of placing some value in there, and a subsequent load from that location will depend on it. The problem is that the value in memory is not directly represented in the DAG, and so there wouldn't be any edge between the store and the load in the graph. They both depend on the address, but both of them are _users_ of the address, so again, that does not introduce a value-based dependency. Chains are used to represent the dependence on factors not included in the DAG, such as accessing the same memory location.

In theCode Generator <http://releases.llvm.org/4.0.0/docs/CodeGenerator.html&gt; documentation, they describe that chains should be used with instructions that have side effects loads, stores, calls, etc. I guess I am confused to as why those instructions need chains. For example, won't loads have a dependency on address to ensure they are only scheduled after address generation.

Yes.

And stores will have dependencies and addresses and results to ensure they only occur after those values are created.

Yes.

Is it because of memory disambiguation causing us to be conservative and needing to ensure that certain store/loads aren't re-ordered respect to each other?

Yes.

I guess the real question is when I include chains for operations and when I want to return chains from operations (especially intrinsics). For example, with the backend, when I am inserting Loads from the stacks, I don't want to chain them all together for performance, right, since it doesn't matter when the loads are scheduled (as long as it is before the use). But I should chain them to the incoming chain from LowerFormalArguments parameter.

The general answer is, if there are dependencies that cannot be preserved by looking only at the def/use (or producer/user) relationships.

On somewhat related note, take this example DAG https://i.stack.imgur.com/RQRpq.gif, why does copyfromreg need a chain input?

CopyFromReg usually reads something from a physical register, and physical registers are treated like memory, i.e. their contents are not tracked.

-Krzysztof