[LLVMdev] trig language-like code generator generator

[Chris Lattner]

On Mon, 25 Apr 2005, Tzu-Chien Chiu wrote:
> i'd like to know what progress you guys have made (not on cvs?).

Everything is in CVS.  Noone is currently working on automating the 
pattern matching generator process yet.  Before doing that, there are a 
few changes we want to make to the SelectionDAG interface.  In particular, 
right now, the selection process basically works like this:

#1. Convert LLVM code to the Selection DAG (and simplify it)
#2. Legalize the selection DAG to only use operations the target supports
     (and simplify the result)
#3. Use ad-hoc .cpp files to convert the selection dag to a stream of
     linearized machine basic blocks and machine instructions.

Before automating step #3, we want to change it so that the process looks 
like this:

#1. (as above)
#2. (as above)
#3. Use ad-hoc .cpp files (adapted from our current ones obviously) to
     convert from the target-independent DAG to a target specific DAG.
     This is the "instruction selection is tree/dag covering" approach to
     instruction selection.  The output of this is a DAG.
#4. Use an algorithm seperate from #3 to pick an ordering (i.e. schedule)
     of the dag nodes and convert them to machine instructions/mbb's.

Once we do this separation, automating #3 is much easier (it needs to know 
less about how the target handles instructions and it makes it easier to 
describe the pattern matching operations).

> i don't want to re-invent wheels, and the existing many code generator
> generators. i am evaluating many possbile code generation libraries.
> at present i give me preferrence to "Prop":
>
>  http://www.cs.nyu.edu/leunga/www/prop.html
> and it's portable too.

Interesting.  I wasn't aware of this work.  Our plan wasn't to encode the 
tree pattern matches directly in the .cpp files (as I believe prop does). 
Instead, we plan to encode the patterns for each instruction in the .td 
files, which are parsed by the tablegen tool.  Tablegen then parses these 
files and emits various chunks of the code generator.  It would emit the 
instruction selector from the patterns in the .td file.

-Chris


> On 4/25/05, Chris Lattner <sabre at nondot.org> wrote:
>> On Mon, 25 Apr 2005, Tzu-Chien Chiu wrote:
>>> http://portal.acm.org/citation.cfm?id=75700
>>
>> Oh, tWig.  :)  Yes, tree pattern matching is exactly the direction we are
>> heading.  We are slowly making the code generators more and more
>> automatically generated as time goes on.  The SelectionDAG infrastructure
>> is mean to support exactly this (perform Tree or DAG pattern matching on
>> the optimized DAG instead of on the LLVM code).
>>
>> This is described here:
>> http://llvm.cs.uiuc.edu/docs/CodeGenerator.html
>>
>> Currently, we use simple greedy bottom-up matchers that are manually
>> written in the <target>ISelPattern.cpp file.  The plan is to extend this
>> by allowing targets to write the DAG pattern for each instruction in the
>> .td files, then build use an optimal code generator generator to emit the
>> matching code.
>>
>> This processes of increased automation has been happening slowly over the
>> years, but we've made good progress.  Are you interested in helping out?
>>
>> -Chris
>>
>>> On 4/25/05, Chris Lattner <sabre at nondot.org> wrote:
>>>> On Sun, 24 Apr 2005, Tzu-Chien Chiu wrote:
>>>>> i'd like to know if there is any plan or existing work to add a Aho's
>>>>> trig language like code generator generator?
>>>>
>>>> Trig is a code generator generator?  Is there any documentation for it
>>>> available anywhere?
>>>>
>>>> -Chris
>>>>
>>>>> "...If you are starting a new port, we recommend that you write the
>>>>> instruction selector using the SelectionDAG infrastructure."
>>>>>
>>>>> any other things i should know before i write one?
>>>>>
>>>>> thank you.
>>>>>
>>>>> _______________________________________________
>>>>> LLVM Developers mailing list
>>>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>>>> http://mail.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>>>
>>>>
>>>> -Chris
>>>>
>>>> --
>>>> http://nondot.org/sabre/
>>>> http://llvm.cs.uiuc.edu/
>>>>
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://mail.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>
>> -Chris
>>
>> --
>> http://nondot.org/sabre/
>> http://llvm.cs.uiuc.edu/
>>
>

-Chris

-- 
http://nondot.org/sabre/
http://llvm.cs.uiuc.edu/