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 <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. 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 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170629/f251acd8/attachment.html>
Hi Dilan, On 29 June 2017 at 10:16, Dilan Manatunga via llvm-dev <llvm-dev at lists.llvm.org> wrote:> 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.
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