How can modern compiler optimization convert recursion into returning a constant?

  • A+
Category:Languages

When I compile the following simple recursion code with g++, the assembly code simply returns i, as if g++ can do some algebra tricks as humans can.

int Identity(int i) {   if (i == 1)     return 1;   else     return Identity(i-1)+1; } 

I don't think this optimization is about tail recursion, and apparently, g++ must at least do these two things:

  1. If we pass a negative value, this code will fall into a infinite loop, so is it valid for g++ to eliminate this bug?
  2. While it is possible to enumerate all values from 1 to INT_MAX, and then g++ can tell that this function shall return i, apparently g++ uses a smarter detection method since the compilation process is pretty fast. Therefore my problem is, how does the compiler optimization do that?

How to reproduce

% g++ -v gcc version 8.2.1 20181127 (GCC)  % g++ a.cpp -c -O2 && objdump -d a.o Disassembly of section .text: 0000000000000000 <_Z8Identityi>:    0:   89 f8                   mov    %edi,%eax    2:   c3 

Updated: Thanks to many person for answering the problem, and I collect some discussions and update here.

  1. The compiler uses some method to know that passing negative values leads to UB, maybe compile uses the same method to do the algebra tricks.
  2. About the tail recursion: According to wiki, my former code is NOT the tail recursion form. I have tried the tail recursion version and gcc generates the correct while loop. However, it cannot just return i as my former code does.
  3. Someone points out that the compiler might try to "prove" f(x) = x but I still do not know the actual optimization name is used. I am interested in the exact name of such optimization, such as common sub-expression (CSE) or some combination of them or whatever.

Updated + answered: Thanks to the answer below (I have marked it helpful, and also check the answer from manlio), I guess I find how compiler can do this in an easy way. Please see the example below. First, modern gcc can do something more powerful then tail recursion, so the code is converted into something like this:

// Equiv to return i int Indetity_v2(int i) {   int ans = 0;   for (int i = x; i != 0; i--, ans++) {}   return ans; } // Equiv to return i >= 0 ? i : 0 int Indetity_v3(int x) {   int ans = 0;   for (int i = x; i >= 0; i--, ans++) {}   return ans; } 

(I guess that) compiler can know that ans and i share the same delta and it also knows i = 0 when leaving the loop. Therefore, compiler knows it should return i. In v3, I use the operator GE so compiler also check the sign of input for me. This could be much simpler than I've guessed.

 


gcc is able to make optimizations on recursion even in the case of non tail-recursive calls. I suppose that a lot of common recursive patterns are searched for and then translated into their iterative or closed form counterpart.

You may read this good old short page about (not)-well known optimization facts about gcc.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: