[LLVMdev] trig language-like code generator generator

Chris Lattner sabre at nondot.org
Mon Apr 25 08:33:19 PDT 2005 

On Mon, 25 Apr 2005, Tzu-Chien Chiu wrote:
> the proposed architecture (chris) doesn't seem to attack the phase
> ordering problem. through having independent instruction selection,
> instruction scheduling, and register allocation phases faciliate a
> modular design, but i believe the phase-coupled code generator
> generator high quality code on many architectures. espeically in the
> embedded system like a media/dsp processors with very limited
> resources and highly respects energy saving.

Hrm, can you give a specific example of the problem you are worried about?

> in which direction llvm team heads?

The way I described :)

> you (chris) didn't mention the optimization code in #1 - #4, and i
> cannot find the optimization code in the step 2 and step 4 mentioned
> in:
>  http://llvm.cs.uiuc.edu/docs/CodeGenerator.html#selectiondag_process
> i don't know if the optimization doesn't existing (a doc bug) or you
> just miss them?

The optimizations are currently very simple, in SelectionDAG.cpp.  They 
are currently limited to folding things like (X + 0) -> X and other 
similar things.  Eventually they will become a full file/pass on their 
own.

> another question raises. unlike "coins"
> (http://www.coins-project.org/international/), there is only one high
> level ir (immediate representation) in the llvm. a low-level ir is
> lacked for low-level optimizations like dead code elimination, machine
> idioms and instruction combining. at present these low-level
> optimization passes/modules must be implementation ad hoc for each
> target. there is no low-level target-independent optimization passes.
>
> please correct me if i am wrong.

This is incorrect.  LLVM has two low-level intermediate representations: 
the selection DAG and the MachineInstr/MachineBB representation.  DCE and 
local CSE is implicit in the DAG construction and machine 
idioms/instruction combining are exactly what instruction selection is all 
about!

Other optimization when they exist (e.g. modulo scheduling) will run after 
instruction selection when the machine instrs/machine bb's are available. 
This is the representation we perform register allocation on etc.

-Chris

> On 4/25/05, Chris Lattner <sabre at nondot.org> wrote:
>> 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/
>>
>

-Chris

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

More information about the llvm-dev mailing list