Thu, 10 Sep 2009 12:18:16 +0200

Related articles |
---|

Graph translational grammars for instruction selection and SSA graphs ihusar@fit.vutbr.cz (ihusar) (2009-09-10) |

From: | ihusar <ihusar@fit.vutbr.cz> |

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 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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.