Graph translational grammars for instruction selection and SSA graphs

ihusar <>
Thu, 10 Sep 2009 12:18:16 +0200

          From comp.compilers

Related articles
Graph translational grammars for instruction selection and SSA graphs (ihusar) (2009-09-10)
| List of all articles for this month |

From: ihusar <>
Newsgroups: comp.compilers
Date: Thu, 10 Sep 2009 12:18:16 +0200
Organization: FIT VUT
Keywords: analysis, question
Posted-Date: 13 Sep 2009 20:06:09 EDT

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
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: 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 Again, I would not like to
reinvent the wheel, so if you know about such approaches, please let
me know.

Thank you
    Adam Husar

Post a followup to this message

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