Loop Tiling in the Presence of Exceptions

Authors Abhilash Bhandari, V. Krishna Nandivada



PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2015.124.pdf
  • Filesize: 1.15 MB
  • 25 pages

Document Identifiers

Author Details

Abhilash Bhandari
V. Krishna Nandivada

Cite AsGet BibTex

Abhilash Bhandari and V. Krishna Nandivada. Loop Tiling in the Presence of Exceptions. In 29th European Conference on Object-Oriented Programming (ECOOP 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 37, pp. 124-148, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.ECOOP.2015.124

Abstract

Exceptions in OO languages provide a convenient mechanism to deal with anomalous situations. However, many of the loop optimization techniques cannot be applied in the presence of conditional throw statements in the body of the loop, owing to possible cross iteration control dependences. Compilers either ignore such throw statements and apply traditional loop optimizations (semantic non-preserving), or conservatively avoid invoking any of these optimizations altogether (inefficient). We define a loop optimization to be xception-safe, if the optimization can be applied even on (possibly) exception throwing loops, in a semantics preserving manner. In this paper, we present a generalized scheme to do exception-safe loop optimizations and present a scheme of optimized exception-safe loop tiling (oESLT), as a specialization thereof. oESLT tiles the input loops, assuming that exceptions will never be thrown. To ensure the semantics preservation (in case an exception is thrown), oESLT generates code to rollback the updates done in the advanced iterations (iterations that the unoptimized code would not have executed, but executed speculatively by the oESLT generated code) and safely-execute the delayed iterations (ones that the unoptimized code would have executed, but not executed by the code generated by oESLT). For the rollback phase to work efficiently, oESLT identifies a minimal number of elements to backup and generates the necessary code. We implement oESLT, along with a naive scheme (nESLT, where we backup every element and do a full rollback and safe-execution in case an exception is thrown), in the Graphite framework of GCC 4.8. To help in this process, we define a new program region called ESCoPs (Extended Static Control Parts) that helps identify loops with multiple exit points and interface with the underlying polyhedral representation. We use the popular PolyBench suite to present a comparative evaluation of nESLT and oESLT against the unoptimized versions.
Keywords
  • Compiler optimizations
  • semantics preservation
  • exceptions
  • loop-tiling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. M. Allen and S. Horwitz. Slicing java programs that throw and catch exceptions. In PEPM, pages 44-54, 2003. Google Scholar
  2. R. Baghdadi, A. Cohen, S. Verdoolaege, and K. Trifunović. Improved loop tiling based on the removal of spurious false dependences. TACO, 9(4):52:1-52:26, 2013. Google Scholar
  3. C. Bastoul. Code generation in the polyhedral model is easier than you think. In PACT, pages 7-16, Juan-les-Pins, Sep 2004. Google Scholar
  4. A. A. Belevantsev, S. S. Gaisaryan, and V. P. Ivannikov. Construction of speculative optimization algorithms. Program. Comput. Softw., 34(3):138-153, 2008. Google Scholar
  5. M.-W. Benabderrahmane, L.-N. Pouchet, A. Cohen, and C. Bastoul. The polyhedral model is more widely applicable than you think. In CC, LNCS, 2010. Google Scholar
  6. C. Bienia, S. Kumar, J. Pal Singh, and K. Li. The parsec benchmark suite: Characterization and architectural implications. In PACT, pages 72-81, New York, NY, USA, 2008. ACM. Google Scholar
  7. R. Bodík, R. Gupta, and V. Sarkar. ABCD: eliminating array bounds checks on demand. In PLDI, pages 321-333. ACM, 2000. Google Scholar
  8. M. G. Burke, J. Choi, S. Fink, D. Grove, M. Hind, V. Sarkar, M. J. Serrano, V. C. Sreedhar, H. Srinivasan, and J. Whaley. The Jalapeño Dynamic Optimizing Compiler for Java. In JAVA, pages 129-141, 1999. Google Scholar
  9. J. Choi, D. Grove, M. Hind, and V. Sarkar. Efficient and precise modeling of exceptions for the analysis of Java programs. SE Notes, 24(5):21-31, 1999. Google Scholar
  10. J. Collard. Automatic parallelization of while-loops using speculative execution. International Journal of Parallel Programming, 23(2):191-219, 1995. Google Scholar
  11. P. Feautrier. Dataflow analysis of array and scalar references. International Journal of Parallel Programming, 20, 1991. Google Scholar
  12. K. Fraser and T. Harris. Concurrent programming without locks. ACM Trans. Comput. Syst., 25(2), May 2007. Google Scholar
  13. C. Fu and B. G. Ryder. Exception-chain analysis: Revealing exception handling architecture in Java server applications. In ICSE, pages 230-239. IEEE, 2007. Google Scholar
  14. M. Gupta, J-D Choi, and M. Hind. Optimizing Java programs in the presence of exceptions. In ECOOP, pages 422-446. Springer-Verlag, 2000. Google Scholar
  15. J. L. Henning. SPEC CPU2006 benchmark descriptions. SIGARCH Comput. Archit. News, 34(4):1-17, September 2006. Google Scholar
  16. M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In ISCA, pages 289-300. ACM, 1993. Google Scholar
  17. IBM. XL C/C++ Compiler. URL: http://www-03.ibm.com/software/products/en/xlcpp-aix.
  18. K. Ishizaki, M. Kawahito, T. Yasue, M. Takeuchi, T. Ogasawara, T. Suganuma, T. Onodera, H. Komatsu, and T. Nakatani. Design, Implementation, and Evaluation of Optimizations in a Just-in-time Compiler. In JAVA, pages 119-128, 1999. Google Scholar
  19. D. Jackson and E. J. Rollins. Chopping: A generalization of slicing. Technical Report CMU-CS-94-169, Carnegie Mellon University, Pittsburgh, PA, USA, 1994. Google Scholar
  20. R. Johnson, D. Pearson, and K. Pingali. The program structure tree: Computing control regions in linear time. In PLDI, pages 171-185, 1994. Google Scholar
  21. J. Lin, W. Hsu, P. Yew, R. D. Ju, and T. Ngai. Recovery code generation for general speculative optimizations. TACO, 3(1):67-89, 2006. Google Scholar
  22. V. V. Mikheev, S. A. Fedoseev, V. V. Sukharev, and N. V. Lipsky. Effective enhancement of loop versioning in java. In CC, pages 293-306, 2002. Google Scholar
  23. J. E. Moreira, S. P. Midkiff, and M. Gupta. From flop to megaflops: Java for technical computing. TOPLAS, 22(2):265-295, 2000. Google Scholar
  24. S. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997. Google Scholar
  25. V. K. Nandivada and S. Jagannathan. Dynamic state restoration using versioning exceptions. HOSC, 19(1):101-124, 2006. Google Scholar
  26. V. K. Nandivada, J. Shirako, J. Zhao, and V. Sarkar. A Transformation Framework for Optimizing Task-Parallel Programs. TOPLAS, 35(1):3:1-3:48, April 2013. Google Scholar
  27. L. N. Pouchet. PolyBench: The Polyhedral Benchmark suite. Google Scholar
  28. L. Renganarayanan, D. Kim, M. M. Strout, and S. Rajopadhye. Parameterized loop tiling. TOPLAS, 34(1):3:1-3:41, May 2012. Google Scholar
  29. H. Rong, Z. Tang, R. Govindarajan, A. Douillet, and G. R. Gao. Single-dimension software pipelining for multidimensional loops. TACO, 4(1), March 2007. Google Scholar
  30. S. Sinha and M. J. Harrold. Analysis and testing of programs with exception-handling constructs. IEEE TSE, 26(9):849-871, September 2000. Google Scholar
  31. Y. Song and Z. Li. New tiling techniques to improve cache temporal locality. In PLDI, pages 215-228, New York, NY, USA, 1999. ACM. Google Scholar
  32. R. M. Stallman and GCC DeveloperCommunity. Using The GNU Compiler Collection: A GNU Manual For GCC Version 4.8.0. CreateSpace, Paramount, CA, 2013. Google Scholar
  33. S. Verdoolaege. ISL: An integer set library for the polyhedral model. In ICMS, pages 299-302, 2010. Google Scholar
  34. T. Würthinger, C. Wimmer, and H. Mössenböck. Array bounds check elimination in the context of deoptimization. Sci. Comput. Program., 74(5-6):279-295, Mar 2009. Google Scholar
  35. J. Xue. Loop Tiling for Parallelism. Kluwer Academic Publishers, 2000. Google Scholar
  36. H. Yun, J. Kim, and S. Moon. Optimal software pipelining of loops with control flows. In ICS, pages 117-128. ACM, 2002. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail