17 Dec 1995 00:19:55 -0500

Related articles |
---|

[6 earlier articles] |

Re: Value range tracing bernecky@eecg.toronto.edu (1995-12-09) |

Re: Value range tracing creusil@cri.ensmp.fr (1995-12-09) |

Value range tracing deaeni@auto-trol.com (1995-12-09) |

Re: Value range tracing gough@dstc.qut.edu.au (John Gough) (1995-12-09) |

Re: Value range tracing jason@reflections.com.au (Jason Patterson) (1995-12-09) |

Re: Value range tracing bill@amber.ssd.hcsc.com (1995-12-09) |

Re: Value range tracing vadik@cs.umd.edu (1995-12-17) |

Re: Value range tracing mab@wdl.loral.com (1995-12-17) |

From: | vadik@cs.umd.edu (Vadim Maslov) |

Newsgroups: | comp.compilers |

Date: | 17 Dec 1995 00:19:55 -0500 |

Organization: | U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742 |

References: | 95-12-014 95-12-026 |

Keywords: | analysis, optimize |

[re value range tracing]

Henry Baker <hbaker@netcom.com> wrote:

*>3. You typically still only solve the 'first-order' problem, where the*

*>endpoints of all the ranges are _compile-time constants_. Unfortunately,*

*>most of the really important problems have ranges in which one of the*

*>endpoints is not known at compile time -- e.g., an array passed to a subroutine*

*>as an argument. Solving this class of problems bumps the complexity up*

*>by a lot.*

You can check out my paper obtainable from

ftp://ftp.cs.umd.edu/pub/cyrillic/papers/value_prop.

It was presented at ICS '95.

The paper goes further than range of values limited by constants.

It allows to propagate a set of values that can be described by affine

constraints (which we can do thanks to Presburger arithmetic solver

and Omega test by Bill Pugh).

%A Vadim Maslov

%T Enhancing Array Dataflow Dependence Analysis

%T with On-Demand Global Value Propagation

%R CS-TR-3310.1

%D December, 1994

%W Omega

%X As recent studies show, state-of-the-art parallelizing compilers

produce no noticeable speedup for 9 out of 12 PERFECT benchmark codes,

while the speedup that was reached by manually applying certain

automatable techniques ranges from 10 to 50. In this paper we

introduce the {\em Global Value Propagation} algorithm that unifies

several of these techniques.

%X Global propagation is performed using program abstraction called {\em

Value Flow Graph (VFG)}. VFG is an acyclic graph in which vertices

and arcs are parametrically specified using {\em F-relations}. The

distinctive features of our propagation algorithm are: (1) It

propagates not only values carried by scalar variables, but also

values carried by {\em individual array elements}. (2) We do not have

to transform a program in order to use propagation results in program

analysis.

%X In this paper we focus on use of the VFG and global value propagation

in array dataflow analysis. F-relations are used to represent values

produced by {\em uninterpreted function symbols} that appear in

dependence problems for non-affine program fragments. Global value

propagation helps us to discover that some of these functions are in

fact affine.

Best regards,

Vadim Maslov

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.