 |
|
| Computers Forum Index » Computer Compilers » Graph translational grammars for instruction selection... |
|
Page 1 of 1 |
|
| Author |
Message |
| ihusar... |
 Posted: Thu Sep 10, 2009 2:18 pm |
|
|
|
Guest
|
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 |
|
|
| Back to top |
|
|
|
|
|
All times are GMT
The time now is Sun Nov 29, 2009 11:58 pm
|
|