Re: Conversion Optimization (Anton Ertl)
13 Dec 2004 02:04:17 -0500

          From comp.compilers

Related articles
Conversion Optimization (2004-12-01)
Re: Conversion Optimization (TOUATI Sid) (2004-12-11)
Re: Conversion Optimization (2004-12-13)
| List of all articles for this month |

From: (Anton Ertl)
Newsgroups: comp.compilers
Date: 13 Dec 2004 02:04:17 -0500
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 04-12-017
Keywords: optimize
Posted-Date: 13 Dec 2004 02:04:17 EST (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:

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

Post a followup to this message

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