Tue, 26 Jan 1993 16:27:02 GMT

Related articles |
---|

Loop-carried dependence analysis for scalar variables haab@crhc.uiuc.edu (1993-01-23) |

Re: Loop-carried dependence analysis for scalar variables paco@cs.rice.edu (Paul Havlak) (1993-01-25) |

Re: Loop-carried dependence analysis for scalar variables paco@cs.rice.edu (1993-01-26) |

Newsgroups: | comp.compilers |

From: | paco@cs.rice.edu (Paul Havlak) |

Organization: | Compilers Central |

Date: | Tue, 26 Jan 1993 16:27:02 GMT |

Keywords: | optimize, analysis, parallel, bibliography |

References: | 93-01-169 |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.