Hi all,
i work on a compiler whose frontend emits a graph-based intermediate representation. These graphs are digraphs (when you an entire source-level procedure is mapped) or DAGs (at a basic-block scope).
What i want to do is to transform such graphs (the computational DAGs would be the simple case) using the minimum number of common subexpression eliminations (CSEs) so that the resulting digraph/DAG is planar. After applying these CSEs, the original graph can be considered to be split into a collection of data-flow trees at the common subexpression boundary. I mean that each resulting connected component should be planar.
Assume the computational graph defined by these statements: x = a * b + c; y = a * b + d; then you have a single CSE, t = a*b, and the resulting computation DAG is defined by 3 data-flow trees (one for each statement): t = a * b; x = t + c; y = t + d;
In general, CSEs can be split to multiple trees (k + 1 trees, where k is the outdegree of the common subexpression node.
This problem has many variants; just to name a few in a single EBNF-like attribution:
<< Partial CSE for [upward] (digraph|DAG) planarization >>
I would gladly accept any help and advice on my problem ^_^
Best regards, Nikolaos Kavvadias
