Re: Loop-carried dependence analysis for scalar variables

        Someone asked in private mail:


> What do you do about arrays in the SSA form -- the treatment in the TOPLAS
> article was very unclear.


        I don't think that there's a definitive answer yet. What one really
wants is a dataflow form for subarrays, so that definitions of disjoint
subarrays aren't ordered even if they reach the same use.
        What we do, and what the PTRAN group does [1] is treat all ambiguous
definitions -- ones that modify part of the object or that only possibly
modify the object -- as uses and killing defs. Ambiguous definitions
include assignments to potential aliases, possible modifications at call
sites, and partial array assignments. For the partial array assignments,
this approach can be viewed as replacing


A[I] = foo();


with


A = g(A);


where g(A) reads in all of A and replaces A[I] with foo()


        I have implemented this method, but we're only just starting to use it
in array dependence analysis. The next step would be to come up with an
algorithm using this form and a subscript tester to build a more
dataflow-like array dependence graph than is currently common.
        Rosene [2] and Pugh & Wonnacott [3] seem to be the best references so
far on building dependence graphs with fewer non-dataflow (redundant
transitive) edges. Neither uses SSA form.
        Parsons Selke [3] has a PDG form for arrays that she found useful for
reasoning about abstract semantics. I haven't had a chance to deeply
consider the integration of this form and SSA form for use in our system.


[1] according to a presentation by Michael Burke at the December 1990
        International Workshop on Compilers for Parallel Computers in
        Paris, France


[2] @phdthesis{Rose:Dissertation,
        Author={C. M. Rosene},
        Title={Incremental Dependence Analysis},
        Month={March},
        Year={1990},
        school={Rice University},
        Note={Available as Rice COMP TR90-112},
        ignore={ } }


[3] Bill Pugh, David Wonnacott, "Eliminating False Data Dependences
        using the Omega Test," SIGPLAN PLDI '92


[4] @phdthesis{Selke:Dissertation,
        Author={Rebecca Parsons Selke},
        Title={A Semantic Framework for Program Dependence},
        Year={1992},
        school={Rice University},
        ignore={ } }
----
Paul Havlak Dept. of Computer Science
Graduate Student Rice University, Houston TX 77251-1892
PFC/ParaScope projects (713) 527-8101 x2738 paco@cs.rice.edu
--

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