[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 

> 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 

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.


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



More information about the llvm-dev mailing list