3 ms·
Registers are also the nodes in the DAG of evaluation. Superscalar execution relies on having multiple edges active over time. Thus, good register allocation wo
by barrkel 10y ago
Registers are also the nodes in the DAG of evaluation. Superscalar execution relies on having multiple edges active over time. Thus, good register allocation won't have bottlenecks, and won't make the evaluation DAG look like a series of linked lists.
There's a nice overview for people with a passing interest here: http://www.lighterra.com/papers/basicinstructionscheduling/ http://www.lighterra.com/papers/basicinstructionscheduling/
- techdragon 10y agoHow did I go so far without hearing the path of execution described as a DAG. Damn that's a useful concept. I might start prototyping some things in DAG notation just to avoid ever forgetting this conceptual abstraction.
- barrkel 10y agoExpressions are DAGs after common subexpression elimination. DAGs are what you get when you symbolically evaluate expressions on a stack machine without backward edges in control flow. Leave out the backward edges and the phi nodes they create, and you get DAGs from SSA form as well (but sequencing has information that you lose).
- qznc 10y agoYou might be interested in "FIRM—A Graph-Based Intermediate Representation" http://pp.ipd.kit.edu/publication.php?id=braun11wir http://pp.ipd.kit.edu/publication.php?id=braun11wir (I'm one of the authors)