AMD 250 manual Recursive Functions, 133

25112 Rev. 3.06 September 2005 Software Optimization Guide for AMD64 Processors

6.5Recursive Functions

Optimization

Use care when writing recursive functions.

Application

This optimization applies to:

•32-bit software

•64-bit software

Rationale

Returns are predicted as described in “Pairing CALL and RETURN,” so recursive functions should be written carefully. If there are only recursive function calls within the function as shown in the following example, the return address for each iteration of the recursive function is properly predicted.

Preferred

long fac(long a)

{

if (a == 0) { return (1);

} else {

return (a * fac(a – 1));

}

}

If there are any other calls within the recursive function (except to itself) as shown in the next example, some returns can be mispredicted. If the number of recursive function calls plus the number of nonrecursive function calls within the recursive function is greater than 12, the return stack does not predict the correct return address for some of the returns once the recursion begins to unwind.

Chapter 6 Branch Optimizations 133