Abstract: As part of its type-safety regime, the Java semantics require precise exception at runtime when programs attempt out-of-bound array accesses. In general, this requires a dynamic bounds check each time an array element is accessed, which limits the performance of array intensive scientific applications implemented in Java. However, if it can be proven that the array index is within the bounds of the array, the check can be eliminated. We present a new algorithm based on extended Static Single Assignment (eSSA) form that builds a constraint system representing control flow qualified, linear constraints among program variables derived from program statements. Our system then derives relationships among variables, and provides a verifiable proof of its conclusions. This proof can be verified by a runtime system to minimize the analysis’ performance impact. Our system simultaneously considers both control flow and data flow when analyzing the constraint system, handles general linear inequalities instead of simple difference constraints, and provides verifiable proofs for its claims. We present experimental results demonstrating that this method eliminates more bounds checks than prior approaches with minimal overhead during JIT compilation. Furthermore our algorithm increased the speed at which the Java benchmarks executed by up to 16%.

Brief Biography of the Speaker:
Kleanthis Psarris is Professor and Chair of the Department of Computer Science at the University of Texas at San Antonio. He received his B.S. degree in Mathematics from the National University of Athens, Greece in 1984. He received his M.S. degree in Computer Science in 1987, his M.Eng. degree in Electrical Engineering in 1989 and his Ph.D. degree in Computer Science in 1991, all from Stevens Institute of Technology in Hoboken, New Jersey. His research interests are in the areas of Parallel and Distributed Systems, Programming Languages and Compilers, and High Performance Computing. He has designed and implemented state of the art program analysis and compiler optimization techniques and he developed compiler tools to increase program parallelization and improve execution performance on advanced computer architectures. He has published extensively in top journals and conferences in the field and his research has been funded by the National Science Foundation and Department of Defense agencies. He is an Editor of the Parallel Computing journal. He has served on the Program Committees of several international conferences including the ACM International Conference on Supercomputing (ICS) in 1995, 2000, 2006 and 2008, the IEEE International Conference on High Performance Computing and Communications (HPCC) in 2008, 2009, and 2010, and the ACM Symposium on Applied Computing (SAC) in 2003, 2004, 2005 and 2006.