Re: Value range tracing

[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


--

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