llvm dev - Apr 2005 - [LLVMdev] trig language-like code generator generator

i'd like to know what progress you guys have made (not on cvs?).

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.

are there any other good library you could recommend?



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

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/

Hi,
When you write a program which uses the "qsort()" library function,
You
also have to provide an implementation of a compare
funtion. Now when we convert our program into  bc and then execute it, I 
get the number of times all basic blocks are executed.
But since the comparison function is called from within the std function 
"qsort()", I don't get the number of times the compare
function is executed.
Is there a way to get this information ?
Thanks,
Abhijit Ray

On Mon, 25 Apr 2005, Abhijit Ray wrote:
> Hi,
> When you write a program which uses the "qsort()" library
function, You also
> have to provide an implementation of a compare
> funtion. Now when we convert our program into  bc and then execute it, I
get
> the number of times all basic blocks are executed.
> But since the comparison function is called from within the std function 
> "qsort()", I don't get the number of times the compare
> function is executed.
> Is there a way to get this information ?
Yes.

Change the "#if 0" to "#if 1" in
runtime/GCCLibraries/libc/qsort.c.

In that directory, run 'make; make install', then recompile your
program.

-Chris

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

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