Re: Value range tracing (Vadim Maslov)
17 Dec 1995 00:19:55 -0500

          From comp.compilers

Related articles
[6 earlier articles]
Re: Value range tracing (1995-12-09)
Re: Value range tracing (1995-12-09)
Value range tracing (1995-12-09)
Re: Value range tracing (John Gough) (1995-12-09)
Re: Value range tracing (Jason Patterson) (1995-12-09)
Re: Value range tracing (1995-12-09)
Re: Value range tracing (1995-12-17)
Re: Value range tracing (1995-12-17)
| List of all articles for this month |

From: (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 <> 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
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
%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.