Graph translational grammars for instruction selection and SSA graphs

Hello guys and ladies,


    In my work, I am trying to generate compiler backend from
instruction set description in an architecture design language called
ISAC (project pages http://www.fit.vutbr.cz/research/groups/lissom/).
For this, I was trying to find a suitable model that describes
instruction set and from which I can generate LLVM backend passes.


One propably suitable model I found is based on context-sensitive
translational graph grammars, where the input grammar is one that
generates compiler's IR control-dataflow graph where nodes are IR
instructions, the output language generates a control-dataflow graph
where nodes are target architecture instructions. My problem here is
that I am not able to find any suitable formalism (most of
graph-grammars work is about context-free graph grammars and
translational grammars seem not to be defined at all).


An attempt to describe rule that represents addition with carry
generation is shown here:
www.stud.fit.vutbr.cz/~xhusar01/graph-graph-add.pdf. This figure shows
context-sensitive graph translation rule where R and C are left-hand
side nonterminals. We can define the graph translational grammar GIS
as a 6-tuple (N, I, O, E, P, S), where the nonterminal set N = Q union
S, Q is set of all processor register classes, I is input alphabet
consisting of compiler's IR instructions and immediate operands, O is
output alphabet consisting of target architecture instructions and
immediate operands, E = {i1, ..., i32, ...} is a set of available data
types that are used to annotate edges present in rules, P is a set of
production rules


My question is: have you read or heard about such an attempt to
describe instructions with graph translational grammars or with
something similar. Also, if the rule example is a little
understandable, don't you know about some suitable context-sensitive
graph translational grammar? (it will be based propably on
gluing/agebraic approach)




My second question is related to SSA-graphs. In my opinion, it would
be nice or at least interesting to have an control-dataflow graph
really defined as a graph (no notion of basic blocks!), there would be
just immediates as leaves and inner nodes would be instructions. There
will be two types of edges: for data dependencies and for control
flow. For example a SSA phi instruction would have one or more
incoming control flow edges and from them it can decide which incoming
dataflow edge will be used as a result. Example is shown here
www.stud.fit.vutbr.cz/~xhusar01/SSA.pdf. Again, I would not like to
reinvent the wheel, so if you know about such approaches, please let
me know.


Thank you
    Adam Husar

Return to the comp.compilers page.
Search the comp.compilers archives again.