Idiom Recognition Framework for Exploiting Complex Hardware Instructions

Processor architectures such as System-Z and POWER offer complex hardware instructions such as CISC and vector instructions (VMX, SSE) in their ISA. To improve performance, an optimizing compiler can recognize a specific idiom in the program and utilize complex instruction(s) instead if the idiom is proven to be semantically equivalent. The framework used by the compiler to perform this optimization is commonly known as idiom recognition. In this talk, we introduce a new idiom recognition framework that detects patterns in input code sequences and replaces them by CISC instructions on System-Z and VMX instructions on POWER architectures. The framework uses the graph topological embedding algorithm to detect patterns in the input code sequence in a flexible manner. This framework allows a pattern to be matched even though it does not exactly match an idiom, thereby allowing transformations in more cases than possible using previous approaches that relied on an exact match. We have implemented this framework in partnership with IBM Research in the IBM Testa Rossa (TR) Just-In-Time (JIT) compiler in the IBM Java Developer Kit for Java 6.0. We obtained a performance improvement of 43% on average on IBM's XML parsers and upto 5x on code-page converters used in IBM's Websphere Application Server on System-Z.

Greg Steffan

Last modified: Fri Aug 31 10:23:38 EDT 2007