Stefan Hepp, and Florian Brandner.

Splitting Functions into Single-Entry Regions

International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES 2014). New Delhi, India. To appear.

Abstract:

As the performance requirements of today's real-time systems are on the rise, system
engineers are increasingly forced to optimize and tune the execution time of
real-time software. Apart from usual optimizations targeting the average-case
performance of a program, the worst-case execution time bound (WCET) delivered
by program analysis tools often has to be improved to meet all the deadlines
and ensure a safe operation of the entire system.

Modern computer architectures pose a significant challenge to this task due to
their high complexity. Out-of-order execution, speculation, caches, buffers,
and branch predictors highly depend on the execution history and are thus
difficult to analyze precisely for WCET analysis tools. Time-predictable
computer architectures overcome this problems by specifically designed
hardware components that are amenable to static program analysis.

A recently proposed alternative for caching executable code, i.e.,
instructions, is the so-called method cache. Instead of a traditional
block-based cache design, the method cache operates on larger code blocks
under the control of the compiler. Due to its design, the analysis of the method
cache is simplified. At the same time, such a system now
highly depends on the compiler and its ability to form suitable code blocks
for caching.

We propose a simple function splitting technique that derives a
suitable partitioning of the basic blocks in a program, targeting
the method cache of the time-predictable processor Patmos. Our approach
exploits dominance properties to form code regions respecting
the method cache's parameters as well as constraints of Patmos' instruction
set architecture. Experimental results show that the method cache can be
competitive with typical instruction cache configurations given the right
splitting.