Our instruction scheduler is based on a block-local data dependency graph that is decomposed into a structure we call a treegraph. The topological ordering of nodes in the treegraph, determines the order in which expression trees in a block will be scheduled.
This necessarily led to the need for some notion of control dependencies: first to ensure that the block terminator was always the last thing scheduled; then to handle instructions with no results that had side effects, as our dead-code elimination pass would remove nodes from the dependency graph which appeared dead, and control dependencies ensured that they were both kept live, and scheduled late in the block.
One thing we didn't handle however, was implicit control dependencies, manifested in the relationship between instructions with side effects - loads and stores, calls to side-effectful functions, etc. If there was no path between them in the dependency graph, they could be reordered relative to one another, which can cause all kinds of weird behavior in the final program. Consider moving a write to memory after a read which expects to observe that write - not good.
This commit refines our existing control dependency handling a bit, by ensuring that within a block, memory reads and writes form implicit control dependencies on other instructions which could affect the state of the world it sees. Memory reads implicitly depend on any writes which appear earlier in the block, ensuring that the writes can't be moved past the read. Memory writes implicitly depend on both previous writes and reads - we don't want to reorder stores relative to each other, and we don't want to move a store above a load, potentially affecting the value observed by that load.
We don't yet have good tests to really determine how drastic of an affect this has on the scheduler, but the one expect test affected by this change (and included in this commit), demonstrates that it does more faithfully preserve the original program order in HIR. For now these extra edges in the dependency graph are placed very conservatively, which reduces the opportunities for the scheduler to place instructions as optimally as possible. We'll need to introduce some static analyses that will let us reason more precisely about the relationships between certain loads/stores, and to determine if a function call actually has memory effects (or other side effects, such as the advice provider); these would let us remove some edges, and bring back optimization opportunities.
Closes #191
@greenhat I've based this on my branch in #241, so we'll want to merge that one first.
Our instruction scheduler is based on a block-local data dependency graph that is decomposed into a structure we call a treegraph. The topological ordering of nodes in the treegraph, determines the order in which expression trees in a block will be scheduled.
This necessarily led to the need for some notion of control dependencies: first to ensure that the block terminator was always the last thing scheduled; then to handle instructions with no results that had side effects, as our dead-code elimination pass would remove nodes from the dependency graph which appeared dead, and control dependencies ensured that they were both kept live, and scheduled late in the block.
One thing we didn't handle however, was implicit control dependencies, manifested in the relationship between instructions with side effects - loads and stores, calls to side-effectful functions, etc. If there was no path between them in the dependency graph, they could be reordered relative to one another, which can cause all kinds of weird behavior in the final program. Consider moving a write to memory after a read which expects to observe that write - not good.
This commit refines our existing control dependency handling a bit, by ensuring that within a block, memory reads and writes form implicit control dependencies on other instructions which could affect the state of the world it sees. Memory reads implicitly depend on any writes which appear earlier in the block, ensuring that the writes can't be moved past the read. Memory writes implicitly depend on both previous writes and reads - we don't want to reorder stores relative to each other, and we don't want to move a store above a load, potentially affecting the value observed by that load.
We don't yet have good tests to really determine how drastic of an affect this has on the scheduler, but the one expect test affected by this change (and included in this commit), demonstrates that it does more faithfully preserve the original program order in HIR. For now these extra edges in the dependency graph are placed very conservatively, which reduces the opportunities for the scheduler to place instructions as optimally as possible. We'll need to introduce some static analyses that will let us reason more precisely about the relationships between certain loads/stores, and to determine if a function call actually has memory effects (or other side effects, such as the advice provider); these would let us remove some edges, and bring back optimization opportunities.
Closes #191
@greenhat I've based this on my branch in #241, so we'll want to merge that one first.