tối ưu hóa bởi trình biên dịch trong một chương trình đệ quy

Question

tôi đã thúc đẩy từ câu hỏi tối ưu hóa cuộc gọi đuôi What Is Tail Call Optimization?

Vì vậy, tôi quyết định xem làm thế nào tôi có thể làm điều đó trong đồng bằng C.

Vì vậy, tôi đã viết 2 chương trình thừa , 1 nơi tối ưu hóa cuộc gọi đuôi có thể được áp dụng. Tôi gọi hàm thực tế này là thực tế (n, 1).

unsigned long long int fact(int n, int cont) 
{ 
     if(n == 0) 
      return cont; 

     else return fact(n-1, n * cont); 
} 

Thứ hai là đệ quy bình thường khi cần nhiều khung ngăn xếp.

unsigned long long int fact(int n) 
{ 
    if(n == 0) 
     return 1; 

    else return n * fact(n-1); 
} 

Đây là lắp ráp được tạo ra bởi một trình biên dịch 32 bit cho cựu với -O2

0x8048470 <fact>: push %ebp 
0x8048471 <fact+1>: mov %esp,%ebp 
0x8048473 <fact+3>: mov 0x8(%ebp),%edx 
0x8048476 <fact+6>: mov 0xc(%ebp),%eax 
0x8048479 <fact+9>: test %edx,%edx 
0x804847b <fact+11>: je  0x8048488 <fact+24> 
0x804847d <fact+13>: lea 0x0(%esi),%esi 
0x8048480 <fact+16>: imul %edx,%eax 
0x8048483 <fact+19>: sub $0x1,%edx 
0x8048486 <fact+22>: jne 0x8048480 <fact+16> 
0x8048488 <fact+24>: mov %eax,%edx 
0x804848a <fact+26>: sar $0x1f,%edx 
0x804848d <fact+29>: pop %ebp 
0x804848e <fact+30>: ret  

Đây là lắp ráp được tạo ra bởi một trình biên dịch 32 bit cho sau này với -O2.

0x8048470 <fact>: push %ebp 
0x8048471 <fact+1>: mov %esp,%ebp 
0x8048473 <fact+3>: push %edi 
0x8048474 <fact+4>: push %esi 
0x8048475 <fact+5>: push %ebx 
0x8048476 <fact+6>: sub $0x14,%esp 
0x8048479 <fact+9>: mov 0x8(%ebp),%eax 
0x804847c <fact+12>: movl $0x1,-0x18(%ebp) 
0x8048483 <fact+19>: movl $0x0,-0x14(%ebp) 
0x804848a <fact+26>: test %eax,%eax 
0x804848c <fact+28>: je  0x80484fc <fact+140> 
0x804848e <fact+30>: mov %eax,%ecx 
0x8048490 <fact+32>: mov %eax,%esi 
0x8048492 <fact+34>: sar $0x1f,%ecx 
0x8048495 <fact+37>: add $0xffffffff,%esi 
0x8048498 <fact+40>: mov %ecx,%edi 
0x804849a <fact+42>: mov %eax,%edx 
0x804849c <fact+44>: adc $0xffffffff,%edi 
0x804849f <fact+47>: sub $0x1,%eax 
0x80484a2 <fact+50>: mov %eax,-0x18(%ebp) 
0x80484a5 <fact+53>: movl $0x0,-0x14(%ebp) 
0x80484ac <fact+60>: sub -0x18(%ebp),%esi 
0x80484af <fact+63>: mov %edx,-0x20(%ebp) 
0x80484b2 <fact+66>: sbb -0x14(%ebp),%edi 
0x80484b5 <fact+69>: movl $0x1,-0x18(%ebp) 
0x80484bc <fact+76>: movl $0x0,-0x14(%ebp) 
0x80484c3 <fact+83>: mov %ecx,-0x1c(%ebp) 
0x80484c6 <fact+86>: xchg %ax,%ax 
0x80484c8 <fact+88>: mov -0x14(%ebp),%ecx 
0x80484cb <fact+91>: mov -0x18(%ebp),%ebx 
0x80484ce <fact+94>: imul -0x1c(%ebp),%ebx 
0x80484d2 <fact+98>: imul -0x20(%ebp),%ecx 
0x80484d6 <fact+102>: mov -0x18(%ebp),%eax 
0x80484d9 <fact+105>: mull -0x20(%ebp) 
0x80484dc <fact+108>: add %ebx,%ecx 
0x80484de <fact+110>: add %ecx,%edx 
0x80484e0 <fact+112>: addl $0xffffffff,-0x20(%ebp) 
0x80484e4 <fact+116>: adcl $0xffffffff,-0x1c(%ebp) 
0x80484e8 <fact+120>: mov -0x1c(%ebp),%ebx 
0x80484eb <fact+123>: mov %eax,-0x18(%ebp) 
0x80484ee <fact+126>: mov -0x20(%ebp),%eax 
0x80484f1 <fact+129>: mov %edx,-0x14(%ebp) 
0x80484f4 <fact+132>: xor %edi,%ebx 
0x80484f6 <fact+134>: xor %esi,%eax 
0x80484f8 <fact+136>: or  %eax,%ebx 
0x80484fa <fact+138>: jne 0x80484c8 <fact+88> 
0x80484fc <fact+140>: mov -0x18(%ebp),%eax 
0x80484ff <fact+143>: mov -0x14(%ebp),%edx 
0x8048502 <fact+146>: add $0x14,%esp 
0x8048505 <fact+149>: pop %ebx 
0x8048506 <fact+150>: pop %esi 
0x8048507 <fact+151>: pop %edi 
0x8048508 <fact+152>: pop %ebp 
0x8048509 <fact+153>: ret  

Soạn cả hai chương trình và xem hội đồng được tạo, cả hai chương trình vẫn có cuộc gọi đệ quy. Nhưng, khi tôi biên dịch với -O2 tùy chọn (lắp ráp được đăng ở trên) trong các cựu, tôi thấy không có cuộc gọi đệ quy ở tất cả và vì vậy tôi nghĩ rằng gcc không đuôi tối ưu hóa cuộc gọi thứ.

Nhưng khi biên dịch tùy chọn -O2, nó cũng loại bỏ các cuộc gọi đệ quy và thay vào đó đặt một số lượng lớn các lệnh lắp ráp so với những gì xảy ra trước đây trên -O2.

Tôi muốn hiểu chính xác trình biên dịch đang làm gì sau này, và tại sao nó không thể chuyển đổi thành lắp ráp được tạo bởi cựu ngay cả với O4.

Answer 1

Chương trình 2 thực hiện long long phép tính, số 1 không.

Answer 2

Sự khác biệt là phiên bản đầu tiên sử dụng biến số int cho phép tính, sau đó được mở rộng đến unsigned long long ở cuối, trong khi phiên bản thứ hai sử dụng unsigned long long tất cả các cách.

Answer 3

Trình biên dịch dường như đã tối ưu hóa các cuộc gọi đệ quy thành vòng lặp. Lưu ý rằng mã C của bạn chỉ có các nhánh chuyển tiếp (if-then-else), nhưng trình assembler có các nhánh ngược (các vòng lặp).

Nếu bạn thực sự muốn xem tối ưu hóa cuộc gọi đuôi đang hoạt động, hãy gọi nó là một chức năng khác. Tất nhiên, đó không phải là đệ quy, nhưng trình biên dịch quá thông minh đối với các trường hợp thử nghiệm nhỏ như thế này.