[libre-riscv-dev] building structured CFG

[Luke Kenneth Casson Leighton]

On Mon, Dec 31, 2018 at 9:54 AM Jacob Lifshay <programmerjake at gmail.com> wrote:

> I finally realized that I was way over-complicating the structured
> representation that I need to use for converting from SIMT-style code to
> vectorized code. I'm hoping to have the structured CFG parser/builder
> portion done by tomorrow.

 deep thought, that - got there in the end :)

> All I really needed was to build a DAG of trees with inner nodes being
> loops and leaves being basic blocks with the children sorted in a
> topological order over the original CFG. This structure is the sequence in
> which I need to execute basic blocks in order to properly cover all the
> basic blocks without executing them multiple times by accident for each
> time around the surrounding loop(s).

 is this possible to draw out as a diagram, as part of an update / explanation?

 a (really small!) example which shows how SPIR-V morphs into
vectorised LLVM-IR would be fantastic.

> Since I already have the underlying CFG already, I can just put it in a
> structure like:
>
> pub enum CFGStructureNode {
>     Loop { children: Vec<CFGStructureNode> },
>     Node { node_index: CFGNodeIndex },
> }
>
> type CFGStructure = Vec<CFGStructureNode>;

 i can sort-of see hints here of where that's going.

> CFGNodeIndex is the index of a basic block in the underlying CFG.
> All of the Vecs are stored topologically-sorted over the underlying CFG.
>
> Note that this means the parser won't work on OpenCL SPIR-V without
> modifications since only Vulkan requires OpLoopMerge which I am using to
> determine the loop tree.

 that would be nice to have, later, particularly for being able to do
e.g. crypto-currencies.

l.