CRPC-TR94388-S

Title:	  Give-N-Take -- A Balanced Code Framework

Authors:  R. v. Hanxleden*, K. Kennedy

Date: 	  June 1994

* student author

Keywords:
  Partial redundancy elimination, Data flow analysis, Tarjan
  intervals, Latency hiding, Fortran D, High Performance Fortran

Abstract:

Give-N-Take is a code placement framework which uses a general
producer-consumer concept.  An advantage of Give-N-Take over existing
partial redundancy elimination techniques is its concept of production
REGIONS, instead of single locations, which can be beneficial for
general latency hiding.  Give-N-Take guarantees BALANCED production,
that is, each production will be started and stopped once.  The
framework can also take advantage of production coming "for free," as
induced by side effects, without disturbing balance.  Give-N-Take can
place production either before or after consumption, and it also
provides the option to hoist code out of potentially zero-trip loop
(nest) constructs.  Give-N-Take uses a fast elimination method based
on Tarjan intervals, with a complexity linear in the program size in
most cases.

We have implemented Give-N-Take as part of a Fortran D compiler
prototype, where it solves various communication generation problems
associated with compiling data-parallel languages onto
distributed-memory architectures.

Appeared in:  Proceedings of the ACM SIGPLAN '94 Conference on Program
 	      Language Design and Implementation, Orlando, FL