A balanced code placement framework

Give-N-Take is a code placement framework which uses a generic producer-con sumer mechanism. An instance of this could be a communication step between a processor that computes (produces) some data, and other processors that s ubsequently reference (consume) these data in an expression. An advantage o f Give-N-Take over traditional 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 also guarantees balan ced production, i.e., each production will be started and stopped exactly o nce. The framework can also take advantage of production coming "for free," as induced by side effects, without disturbing balance. Give-N-Take can pl ace production either before or after consumption, and it also provides the option to speculatively hoist code out of potentially zero-trip loop (nest ) constructs. Give-N-Take uses a fast elimination method based on Tarjan in tervals, with a complexity linear in the program size in most cases. We hav e implemented Give-N-Take as part of a Fortran D compiler prototype, where it solves various communication generation problems associated with compili ng data-parallel languages onto distributed-memory architectures.