trig language-like code generator generator

i'd like to know if there is any plan or existing work to add a Aho's
trig language like code generator generator?

"...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.

i'd like to know if there is any plan or existing work to add a Aho's
trig language like code generator generator?

I'm not aware of either the trig language code generator nor any work to
implement it in LLVM.

"...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?

You should read these:

http://llvm.cs.uiuc.edu/docs/WritingAnLLVMBackend.html
http://llvm.cs.uiuc.edu/docs/TableGenFundamentals.html

If you're unsure of how things are implemented, take a look at how
similar things are done in X86, PowerPC, Alpha or IA64, they all have
SelectionDAG-based instruction selectors (*ISelPattern.cpp). If that
doesn't clear things up, ask on the list or IRC channel.

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@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://mail.cs.uiuc.edu/mailman/listinfo/llvmdev

-Chris

yes, i did read those document. but i don't target any existing
hardware. i need a compiler during the hareware design phase (i work
for an ihv). preferrable a bnf syntax/rule/cost-driven and code
generator generator. dynamic programming ones like twig, burg, beg,
etc.

http://portal.acm.org/citation.cfm?id=75700

Oh, tWig. :slight_smile: 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

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?

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

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

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

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.

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 :slight_smile:

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