**Dynamic currency determination in optimized programs**

D. M. Dhamdhere, K. V. Sankaranarayanan

Pages: 1111-1130

DOI: 10.1145/295656.295657

Compiler optimizations pose many problems to source-level debugging of an optimized program due to reordering, insertion, and deletion of code. On such problem is to determine whether the value of a varible is current at a...

**A task- and data-parallel programming language based on shared objects**

Saniya Ben Hassen, Henri E. Bal, Ceriel J. H. Jacobs

Pages: 1131-1170

DOI: 10.1145/295656.295658

Many programming languages support either task parallelism, but few languages provide a uniform framework for writing applications that need both types of parallelism or data parallelism. We present a programming language and system that...

**Finitary fairness**

Rajeev Alur, Thomas A. Henzinger

Pages: 1171-1194

DOI: 10.1145/295656.295659

Fairness is a mathematical abstraction: in a multiprogramming environment, fairness abstracts the details of admissible (“fair”) schedulers; in a distributed environment, fairness abstracts the relative speeds of processors. We argue...

**Space/time-efficient scheduling and execution of parallel irregular computations**

Tao Yang, Cong Fu

Pages: 1195-1222

DOI: 10.1145/295656.295660

In this article we investigate the trade-off between time and space efficiency in scheduling and executing parallel irregular computations on distributed-memory machines. We employ acyclic task dependence graphs to model irregular parallelism...

**Optimizing compilation of CLP( R )**

Andrew D. Kelly, Kim Marriott, Andrew MacDonald, Peter J. Stuckey, Roland Yap

Pages: 1223-1250

DOI: 10.1145/295656.295661

Constraint Logic Programming (CLP) languages extend logic programming by allowing the use of constraints from different domains such as real numbers or Boolean functions. They have proved to be ideal for expressing problems that require...

**Equality-based flow analysis versus recursive types**

Jens Palsberg

Pages: 1251-1264

DOI: 10.1145/295656.295662

Equality-based control-flow analysis has been studied by Henglein, Bondorf and Jørgensen, DeFouw, Grove, and Chambers, and others. It is faster than the subset-based-0-CFA, but also more approximate. Heintze asserted in 1995 that a...

**A new, simpler linear-time dominators algorithm**

Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook

Pages: 1265-1296

DOI: 10.1145/295656.295663

We present a new linear-time algorithm to find the immediate dominators of all vertices in a flowgraph. Our algorithm is simpler than previous linear-time algorithms: rather than employ complicated data structures, we combine the use of...

**Cost-optimal code motion**

Max Hailperin

Pages: 1297-1322

DOI: 10.1145/295656.295664

We generalize Knoop et al.'s Lazy Code Motion (LCM) algorithm for partial redundancy elimination so that the generalized version also performs strength reduction. Although Knoop et al. have themselves extended LCM to strength reduction with...