[LLVMdev] trig language-like code generator generator

[Tzu-Chien Chiu]

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.

in which direction llvm team heads?

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?

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.

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