Re: Conversion Optimization

diablovision@yahoo.com (Ben L. Titzer) writes:
>Is there any work, or any languages, for optimizing the conversion of
>bit patterns. For example, signed / unsigned extension, truncation,
>shifting, etc.
>
>My goal is to write everything in bit patterns and have the compiler
>do the job of scheduling the necessary conversions to / from various
>primitive types as well as masking, shifting, etc.


For optimizing conversions between data representations, you can use
tree parsing. You can find slides for a talk I gave about this at the
Dagstuhl Seminar on Code Optimization in September 2000 here:


http://www.complang.tuwien.ac.at/papers/ertl00dagstuhl.ps.gz


As presented, this works optimally in linear time for data-flow trees.
You typically go into NP-completeness territory once you want to do
this for DAGs (but a linear-time method may still provide good results
in the typical cases with some fine-tuning). Using tree-parsing
methods across (extended) basic blocks is pretty hard, but there's a
paper by Erik Eckstein et al. at Scopes 2003 on the topic.


One other related thing I can think of, for a global version of such
an optimization, is the work by Dhamdhere on load/store placement
based on (IIRC) partial redundancy elimination. If you use his work
with conversion operations instead of loads/stores, you may be able to
perform some of the optimizations you have in mind.


Erik Eckstein, Oliver Koenig, Bernhard Scholz: Code Instruction
Selection Based on SSA-Graphs. SCOPES 2003: 49-65


D. M. Dhamdhere
A usually linear algorithm for register assignment using edge
placement of load and store instructions
Computer Languages, 15(2), pp. 83-94, 1990.


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html

Return to the comp.compilers page.
Search the comp.compilers archives again.