Browse Prior Art Database

Method for limiting save and restore of callee-saved registers

IP.com Disclosure Number: IPCOM000239142D
Publication Date: 2014-Oct-16
Document File: 8 page(s) / 68K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for limiting save and restore of callee-saved registers that includes a new approach to shrink-wrapping.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 23% of the total text.

Page 01 of 8

Method for limiting save and restore of callee-saved registers

When a compiler generates code, the goal is to generate code that runs as fast as possible on the target computer architecture . Often the compiler must make decisions that can affect performance while looking at one portion of the program . In particular,

when one function, say A(), calls another, say B(), should the compiler assume that B() overwrites a particular register? If the compiler assumes that B() will overwrite every register, but it only uses a small number of registers, then there will be more instructions than necessary in A() to save and restore any values that must be live across a call to B(). If the compiler assumes that B() will not overwrite any register, but not many registers need to be preserved across calls to B(), then there will be a lot of extra code in B() to save and restore the registers whose values will not actually be used.

The solution is usually a compromise in which the registers are divided into two groups: callee-saved registers and caller-saved registers. The called-saved registers are those that the compiler will assume will be overwritten on every function call. The caller-saved registers are those that the compiler will assume are not overwritten by a call to another function. The exact division is usually laid out in the application binary interface (ABI) for the particular platform. This division does not completely solve the problem, however. Extra code might be needed as before, but now it should be reduced.

This article addresses the cost of callee-saved registers. To properly understand the problem, consider a function B(), that wants to use a callee-saved register r.

void B() {

...
if (cond) {

...
r = ...' ...
s = r;

} ...

}

When B() returns, r will have to contain the value it had at the start of B(). The simplest way (i.e. the simple method) of

1


Page 02 of 8

accomplishing this is to save the value in r to memory at the start of the procedure, and then reload the value just before returning. The problem with this method is that it saves and restores r, even if r is not used. In the case where cond is false, the load reloads a value that is already in r.

One solution is an algorithm called shrink-wrapping[2]. The idea is to only save callee-saved registers when users are certain those registers will be used. The shrink-wrapping algorithm adds code that saves and restores r at the start and end of each of the if statements. If while running the code cond1, cond2 and cond3 are true most of the time; the process saves and restores three times instead of one.

Another problem is the way shrink-wrapping interacts with code that might unwind the call stack without returning control to the current function. An example of this is a function that might throw a C++ exception. If C() throws a C++ exception, it will not be caught in B(). Currently, in some implementations, the function that actually unwinds the stack is responsible f...