[Mesa-dev] Mesa (shader-work): glsl: introduce ir_binop_all_equal and ir_binop_any_equal, allow vector cmps

[Luca Barbieri]

> Structured flow control is the issue.  What's the solution for getting
> that back out of LLVM?

Well, my idea is the following.

First, break any self loop edges, then do an SCC decomposition of the
CFG, and output the DAG of the SCCs in topological order.
SCCs that have size 1 are basic blocks, so just emit them.
SCCs that have size >1 become loops. Choose the basic block with the
most in-edges from outside the SCC, and make that the loop header.
Now, make all the edges from outside to inside the SCC, and those from
inside to the header, pass through a new basic block after setting an
appropriate flag, which is used by this new basic block to dispatch
them to their "old destinations", thus making all in-edges go to this
single node, making the CFG reducible.
Then, do a similar thing with the out-edges, so that there is a single
"after" node for the loop.
After that, recurse on the graph formed by the SCC minus the original
header, plus the in-edge dispatch node with becomes part of the loop

This will give you a CFG which is composed only of loops and
conditional forward gotos.

Now, process each loop body, which is an acyclic graph after
collapsing nested loops.
Every time a node has two successors, that's an "if".
On each branch, you put those basic blocks that are dominated by the
branch out-edge.
Now, if these blocks have out-edges to a single node, that's the
"endif", and you just recursively process the branches.
Otherwise, "cut" those edges by introducing a new dispatch node with a flag.

A further issues are switch statements.
These can be treated as successive ifs, but the way they are split
affects the conciseness of the result.
The idea here is to split the graph in biconnected components, and see
if any articulation point splits some of the switch cases from the
others.
If so, you generate an if to separate those cases, and recurse.
Post-dominators might also work for this, but it seems biconnected
components are required to handle multiple exits due to breaks and
returns properly

After all this, you rerun all LLVM optimization passes with all parts
that could destroy this structure disabled.

Then, you convert it to GLSL IR or whatever you want.

I have code that does this and seems to work on the tests I did, but
it's not yet in a state where it would be mergeable in LLVM upstream.
In particular, it's hard to get nice clean code, and avoid quadratic algorithms.