एक कंपाइलर इस फैक्टोरियल फ़ंक्शन को कितनी अच्छी तरह अनुकूलित करता है?

Question

तो मैं जीसीसी में O3 पर कुछ जादू देख रहा हूं (वास्तव में मैं क्लैंग का उपयोग कर संकलन कर रहा हूं लेकिन यह जीसीसी के साथ समान है और मैं अनुमान लगा रहा हूं कि ऑप्टिमाइज़र का एक बड़ा हिस्सा जीसीसी से खींच लिया गया था क्लैंग करने के लिए)।

इस सी कार्यक्रम पर विचार करें:

int foo(int n) { 
    if (n == 0) return 1; 
    return n * foo(n-1); 
} 

int main() { 
    return foo(10); 
} 

पहली बात मैं सुंदर वाह-एड (जो भी इस प्रश्न में वाह-एड था - https://stackoverflow.com/a/414774/1068248) था कैसे int foo(int) (एक बुनियादी भाज्य समारोह) compiles एक तंग पाश में। यह इसके लिए एआरएम असेंबली है:

.globl _foo 
    .align 2 
    .code 16 
    .thumb_func _foo 
_foo: 
    mov r1, r0 
    movs r0, #1 
    cbz r1, LBB0_2 
LBB0_1: 
    muls r0, r1, r0 
    subs r1, #1 
    bne LBB0_1 
LBB0_2: 
    bx lr 

ब्लिमी मैंने सोचा। यह बहुत दिलचस्प है! फैक्टोरियल करने के लिए पूरी तरह से तंग लूपिंग। वाह। यह पूंछ कॉल अनुकूलन नहीं है, ठीक है, यह पूंछ कॉल नहीं है। लेकिन ऐसा लगता है कि यह एक बहुत ही अनुकूल अनुकूलन किया है।

अब main को देखो:

.globl _main 
    .align 2 
    .code 16 
    .thumb_func _main 
_main: 
    movw r0, #24320 
    movt r0, #55 
    bx lr 

कि सिर्फ मेरे मन विस्फोट से उड़ा दिया ईमानदार होना। यह पूरी तरह से foo को छोड़कर 3628800 लौटा रहा है जो 10! है।

इससे मुझे वास्तव में एहसास हो जाता है कि आपका कंपाइलर अक्सर आपके कोड को अनुकूलित करने के लिए बेहतर काम कर सकता है। लेकिन यह सवाल उठाता है, यह अच्छी नौकरी कैसे प्रबंधित करता है? तो, किसी को समझा सकता है कि निम्नलिखित अनुकूलन काम (संभवतः प्रासंगिक कोड से लिंक करके):

1. प्रारंभिक foo अनुकूलन एक तंग पाश किया जाना है।

2. अनुकूलन जहां main वास्तव में foo निष्पादित करने के बजाय सीधे परिणाम देता है और परिणाम देता है।

इसके अलावा इस सवाल का एक और दिलचस्प पक्ष प्रभाव कुछ और अधिक दिलचस्प अनुकूलन जो जीसीसी/बजना क्या कर सकते हैं दिखाने के लिए किया जाएगा।

Answer 1

यदि आप gcc -O3 -fdump-tree-all के साथ संकलित करते हैं, तो आप देख सकते हैं कि पहला डंप जिसमें रिकर्सन को लूप में बदल दिया गया है foo.c.035t.tailr1 है। इसका मतलब है कि वही अनुकूलन जो अन्य पूंछ कॉलों को संभालता है, यह थोड़ा विस्तारित मामला भी संभालता है। n * foo(...) या n + foo(...) के रूप में रिकर्सन मैन्युअल रूप से संभालना मुश्किल नहीं है (नीचे देखें), और चूंकि यह वर्णन करना संभव है कि संकलक स्वचालित रूप से उस अनुकूलन को कैसे कर सकता है।

main के अनुकूलन बहुत सरल है: इनलाइनिंग 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1 में इस बंद कर सकते हैं, और अगर सब कुछ एक गुणा के ऑपरेंड स्थिरांक हैं, तो गुणा संकलन समय पर किया जा सकता है।

अद्यतन: यहां बताया गया है कि आप foo से रिकर्सन मैन्युअल रूप से कैसे हटा सकते हैं, जो स्वचालित रूप से किया जा सकता है। मैं यह नहीं कह रहा हूं कि यह जीसीसी द्वारा उपयोग की जाने वाली विधि है, लेकिन यह एक यथार्थवादी संभावना है।

सबसे पहले, एक सहायक कार्य बनाएं।यह foo(n) जैसा व्यवहार करता है, सिवाय इसके कि इसके परिणाम f अतिरिक्त पैरामीटर द्वारा गुणा किए जाते हैं।

int foo(int n) 
{ 
    return foo_helper(n, 1); 
} 

int foo_helper(int n, int f) 
{ 
    if (n == 0) return f * 1; 
    return f * n * foo(n-1); 
} 

फिर, foo_helper की पुनरावर्ती कॉल में foo की पुनरावर्ती कॉल कर देते हैं, और गुणा से छुटकारा पाने के कारक पैरामीटर पर निर्भर हैं।

int foo(int n) 
{ 
    return foo_helper(n, 1); 
} 

int foo_helper(int n, int f) 
{ 
    if (n == 0) return f; 
    return foo_helper(n-1, f * n); 
} 

एक पाश में इस बारी:

int foo(int n) 
{ 
    return foo_helper(n, 1); 
} 

int foo_helper(int n, int f) 
{ 
restart: 
    if (n == 0) return f; 
    { 
     int newn = n-1; 
     int newf = f * n; 
     n = newn; 
     f = newf; 
     goto restart; 
    } 
} 

अंत में, इनलाइन foo_helper:

int foo(int n) 
{ 
    int f = 1; 
restart: 
    if (n == 0) return f; 
    { 
     int newn = n-1; 
     int newf = f * n; 
     n = newn; 
     f = newf; 
     goto restart; 
    } 
} 

(जाहिर है, इस सबसे समझदार रास्ता मैन्युअल समारोह लिखने के लिए नहीं है।)