[llvm-dev] Understanding Chains

[Krzysztof Parzyszek via llvm-dev]

On 6/29/2017 12:16 PM, Dilan Manatunga via llvm-dev wrote:>
> 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> 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

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation