pystencils.flow.canonicalize_flowgraph.CanonicalizeFlowgraph

class pystencils.flow.canonicalize_flowgraph.CanonicalizeFlowgraph

Check a flowgraph for consistency and transform it into canonical form.

A flowgraph must meet the following requirements to be eligible for code generation:

• It has an explicit bottom node \(\bot\) and an explicit top node \(\top\)

• Each node apart from \(\top\) has at least one predecessor (i.e. \(\top\) is the only root)

• Each node has at least one successor (i.e. \(\bot\) is the only sink)

• On each node, each free symbol must be exported by exactly one predecessor (where \(\top\) implicitly exports all symbols that are globally free)

• Each memory location and reduction target is written to no more than once

Instances of this class will check these conditions; rectify some of them if possible, and raise an error otherwise. In particular, CanonicalizeFlowgraph will add explicit bottom and top nodes if these are missing, and introduce edges from \(\top\) to any node with dangling free symbols, and to any node that has no predecessors.

The canonicalizer returns a CanonicalizationResult, containing the canonicalized graph together with its sets of free symbols, exports, and side effects.