C ++ और C # कंपाइलर्स में Peephole microoptimization

स्कूल में, जब हमने समीकरण हल किए या सूत्रों पर विचार किया, तो हमने उन्हें कई बार कम करने की कोशिश की, उदाहरण के लिए, Z = X - (Y + X) को Z = -Y घटा दिया गया। आधुनिक संकलक में, यह तथाकथित पीपहोल अनुकूलन का एक सबसेट है, जिसमें, मोटे तौर पर बोलना, पैटर्न का एक सेट हम भावों को कम करते हैं, किसी विशेष प्रोसेसर के लिए तेजी से निर्देशों को प्रतिस्थापित करते हैं, आदि। इस लेख में, मैंने ऐसे अनुकूलन का संकलन संकलित किया है जो LLVM, GCC और .NET कोर (CoreCLR) स्रोतों में पाए गए थे।

सरल उदाहरणों के साथ शुरू करते हैं:

  X * 1 => X -X * -Y => X * Y -(X - Y) => Y - XX * Z - Y * Z => Z * (X - Y) 

C ++ और C # में अंतिम उदाहरण देखें:

 int Test(int x, int y, int z) { return x * z - y * z; // => z * (x - y) } 

और Clang (LLVM), GCC, MSVC और .NET कोर से कोडांतरक देखें:

सभी तीन सी ++ कंपाइलर (जीसीसी, imul ) ने एक गुणा कम कर दिया (हम केवल एक imul इंस्ट्रक्शन देखते हैं)। C # ने RyuJIT के साथ ऐसा नहीं किया, लेकिन इसके लिए उसे डांटने में जल्दबाजी न करें, बस इतना है कि अनुकूलन का यह वर्ग एक सीमित संरचना में उपलब्ध है। आपको यह समझने के लिए, LLVM में संपूर्ण InstCombine परिवर्तन के कार्यान्वयन में कोड की 30k से अधिक लाइनें (+ DAGCombiner.cpp पर + 20k लाइनें) लगती हैं, इसके अलावा, यह परिवर्तन अक्सर एक लंबे संकलन का कारण बनता है। वैसे, इस अनुकूलन के लिए जिम्मेदार साइट है। जीसीसी में एक विशेष डीएसएल है जो अनुकूलन piphole का वर्णन करता है, यहां एक स्निपेट है )।

मैंने तय किया, लेख के लिए, इस अनुकूलन को C # JIT (मेरी बियर पकड़ो) में लागू करने का प्रयास करने के लिए:

पूर्ण प्रतिबद्धता यहां ईगोरबो / कॉर्क्लर में देखी जा सकती है। आइए अब मेरे सुधार की जाँच करें (दृश्य स्टूडियो 2019 में + डिस्मो:

यह काम करता है! lea + imul जगह imul , imul और add ।

आइए C ++ पर वापस जाएं और इस अनुकूलन को Clang में ट्रैक करें। ऐसा करने के लिए, हमें प्रारंभिक LLVM IR के माध्यम से -emit-llvm -g0 देने के लिए -emit-llvm -g0 , और फिर रूपांतरण के सटीक क्षण को पकड़ने के लिए -O2 -print-before-all -print-after-all पैरामीटर्स का उपयोग करते हुए, अनुकूलक को LLVM को दें। सेट -O2 से गुणा को हटाता है (यह सब अद्भुत संसाधन Godbolt.org पर देखा जा सकता है):

 ; *** IR Dump Before Combine redundant instructions *** define dso_local i32 @_Z5Case1iii(i32, i32, i32) { %4 = mul nsw i32 %0, %2 %5 = mul nsw i32 %1, %2 %6 = sub nsw i32 %4, %5 ret i32 %6 } ; *** IR Dump After Combine redundant instructions *** define dso_local i32 @_Z5Case1iii(i32, i32, i32) { %4 = sub i32 %0, %1 %5 = mul i32 %4, %2 ret i32 %5 } 

आप एलएलवीएम टूल्स - ऑप्ट (ऑप्टिमाइज़र) और एलएलसी (एलएलवीएम आईआर को एसम में संकलित करने के लिए) के साथ गॉडबॉल्ट पर भी मज़े कर सकते हैं:

वापस उदाहरणों के लिए। मुझे जीसीसी में यह बहुत अच्छा उदाहरण मिला।

 X == C - X => false if C is odd 

और यह सच है: यदि (स्थिर, शाब्दिक) तब भी है, उदाहरण के लिए, आप 4 == 8 - 4 लिख सकते हैं। लेकिन अगर 8 के बजाय आप कोई अजीब लिखते हैं, तो आप ऐसा X नहीं खोज सकते जिससे समानता पूरी हो:

IEEE754 स्ट्राइक्स बैक

कई अनुकूलन विभिन्न डेटा प्रकारों के लिए काम करते हैं, उदाहरण के लिए, byte , int , unsigned , float , double । उत्तरार्द्ध के साथ, चीजें इतनी सरल नहीं हैं और IEEE754 विनिर्देशन द्वारा अनुकूलन को नियंत्रित किया जाता है, जो कि A - B - A टू या -B (A * B) * C कम करने पर पागल हो जाएगा। इसे फिर से A * (B * C) टी पर फिर से व्यवस्थित करें। एक। संचालन सहयोगी नहीं हैं। लेकिन आधुनिक संकलक में एक विशेष मोड है जो आपको ऐसे मामलों में कल्पना और सीमा मूल्यों (NaN, + -Inf, + -0.0) की उपेक्षा करने और सुरक्षित रूप से अनुकूलन करने की अनुमति देता है - यह फास्ट मैथ है (C के लिए इस तरह के मोड को जोड़ने के लिए मेरा पीआर अनुरोध यहां पाया जा सकता है) )।

जैसा कि आप देख सकते हैं इन -ffast-math दो और vsubss :

अभिव्यक्तियों के अलावा, ऑप्टिमाइज़र भी गणित से गणितीय कार्यों के साथ बाजीगरी करते हैं। उदाहरण के लिए, संख्या X के मोडुली का उत्पाद संख्या X के उत्पाद के बराबर है:

 abs(X) * abs(X) => X * X 

वर्गमूल हमेशा सकारात्मक होता है:

 sqrt(X) < Y => false, if Y is negative. sqrt(X) < 0 => false 

रूट की गणना क्यों करें, यदि संकलन चरण में दाईं ओर स्थिर वर्ग की गणना करना संभव है ?:

 sqrt(X) > C => X > C * C 

अधिक रूट संचालन:

 sqrt(X) == sqrt(Y) => X == Y sqrt(X) * sqrt(X) => X sqrt(X) * sqrt(Y) => sqrt(X * Y) logN(sqrt(X)) => 0.5*logN(X) 

कुछ और स्कूल गणित:

 expN(X) * expN(Y) -> expN(X + Y) 

और मेरा पसंदीदा अनुकूलन:

 sin(X) / cos(X) => tan(X) 

बोरिंग बिट और बूलियन ऑपरेशन के बहुत सारे:

 ((a ^ b) | a) -> (a | b) (a & ~b) | (a ^ b) --> a ^ b ((a ^ b) | a) -> (a | b) (X & ~Y) |^+ (~X & Y) -> X ^ Y A - (A & B) into ~B & A X <= Y - 1 equals to X < Y A < B || A >= B -> true ...   ! 

निम्न स्तर के अनुकूलन

अनुकूलन का एक सेट है, जो पहली नज़र में t.z के साथ कोई मतलब नहीं रखता है। गणितज्ञ, लेकिन लोहे के अधिक अनुकूल हैं।

 X / 2 => X * 0.5 

गुणा द्वारा विभाजन को प्रतिस्थापित करें:

बेड़े के गुणा के संचालन में आमतौर पर विभाजन की तुलना में बेहतर विलंबता / प्रवाह क्षमता होती है। उदाहरण के लिए, यहां इंटेल हसवेल के विकल्प दिए गए हैं:

गैर-फास्ट-गणित मोड में, इसका उपयोग केवल तभी किया जा सकता है जब स्थिर दो की शक्ति हो।
वैसे, मैंने हाल ही में सी # में इस तरह के अनुकूलन को जोड़ने की कोशिश की। यानी यदि, उदाहरण के लिए, आपको 3 डी मॉडल के साथ एक फ़ाइल खोलने और सभी निर्देशांक को 10 गुना कम करने की आवश्यकता है, तो * 0.1 इस 20-100% तेजी से संभाल लेगा, जो महत्वपूर्ण हो सकता है।

के लिए एक ही तर्क:

 X * 2 => X + X 

शून्य ( test ) के साथ तुलना करना इकाई ( cmp ) की तुलना में बेहतर है - विवरण के लिए मेरा पीआर डॉटनेट / कोरक्लर # 25458 है :

 X >= 1 => X > 0 X < 1 => X <= 0 X <= -1 => X >= 0 X > -1 => X >= 0 

और आपको यह कैसे पसंद है:

 pow(X, 0.5) => sqrt(x) pow(X, 0.25) => sqrt(sqrt(X)) pow(X, 2) => X * X ; 1 mul pow(X, 3) => X * X * X ; 2 mul 

आपको क्या लगता है, mod(X, 4) या X * X * X * X को गिनने के लिए आपको कितने गुणा ऑपरेशन की जरूरत है?

दो! 3 डिग्री की गणना के लिए और साथ ही मामले 4 में हम केवल एक रजिस्टर xmm0 उपयोग xmm0 ।

कई प्रोसेसर एक विशेष निर्देश (FMA) का समर्थन करते हैं, जो आपको एक समय में गुणन और जोड़ प्रदर्शन करने की अनुमति देता है, जबकि लहसुन को सटीकता के साथ बनाए रखना होता है:

 X * Y + Z => fmadd(X, Y, Z) 

मेरे दो और पसंदीदा उदाहरण कुछ एल्गोरिदम को एक निर्देश में बदल रहे हैं (यदि प्रोसेसर इसका समर्थन करता है):

अनुकूलन जाल

मुझे लगता है कि हर कोई समझता है कि आप केवल तीन कारणों से भावनाओं को कम नहीं कर सकते हैं:

• आप कुछ सीमा मूल्यों, अतिप्रवाह, छिपे हुए साइड इफेक्ट्स आदि पर कोड को तोड़ सकते हैं ... बुगज़िला एलएलवीएम में कई इंस्टाग्रामी कीड़े शामिल हैं।
• आदर्श रूप से, अनुकूलन को एक विशिष्ट अनुक्रम में एक साथ काम करना चाहिए।
• जिस अभिव्यक्ति या भागों को आप कम करना चाहते हैं उसका उपयोग कहीं और किया जा सकता है और उनकी कमी से प्रदर्शन में गिरावट आएगी।

आइए अंतिम पैराग्राफ के लिए एक उदाहरण देखें (कंपाइलिंग ऑप्टिमाइज़ करने के लिए भविष्य के निर्देशों में लेख में जासूसी)।

कल्पना कीजिए कि हमारे पास यह कोड है:

 int Foo1(int a, int b) { int na = -a; int nb = -b; return na + nb; } 

हमें तीन ऑपरेशन करने की आवश्यकता है: 0 - a , 0 - b , और na + nb । लेकिन हमारे लिए ऑप्टिमाइज़र इसे दो - return -(a + b); घटा देता है return -(a + b); :

 define dso_local i32 @_Z4Foo1ii(i32, i32) { %3 = add i32 %0, %1 ; a + b %4 = sub i32 0, %3 ; 0 - %3 ret i32 %4 } 

अब कल्पना करें कि हमें वैश्विक वैरिएबल के लिए मध्यवर्ती मान na और nb लिखना होगा:

 int x, y; int Foo2(int a, int b) { int na = -a; int nb = -b; x = na; y = nb; return na + nb; } 

ऑप्टिमाइज़र अभी भी इस पैटर्न को ढूंढता है और अनावश्यक को हटाता है (अपने दृष्टिकोण से) संचालन 0 - a और 0 - b , लेकिन वास्तव में यह पता चला है कि वे आवश्यक हैं! हम वैश्विक चर में इन "अनावश्यक" संचालन के परिणाम लिखते हैं! यह इस कोड की ओर जाता है:

 define dso_local i32 @_Z4Foo2ii(i32, i32) { %3 = sub nsw i32 0, %0 ; 0 - a %4 = sub nsw i32 0, %1 ; 0 - b store i32 %3, i32* @x, align 4, !tbaa !2 store i32 %4, i32* @y, align 4, !tbaa !2 %5 = add i32 %0, %1 ; a + b %6 = sub i32 0, %5 ; 0 - %5 ret i32 %6 } 

तीन के बजाय चार गणितीय संचालन! हमारे आशावादी ने हमें विफल कर दिया और यह आश्वस्त नहीं था कि मध्यवर्ती अभिव्यक्तियाँ जिसे उन्होंने अनुकूलित किया था, अभी भी किसी की ज़रूरत थी। अब आइए C # RuyJIT के आउटपुट पर नज़र डालें, जिसमें ऐसा कोई स्मार्ट ऑप्टिमाइज़ेशन नहीं है:

चार के बजाय तीन ऑपरेशन - C # C ++ :-) की तुलना में तेज़ निकला।!

क्या ऐसे अनुकूलन की आवश्यकता है?

आप कभी नहीं जानते कि संकलक कोड को किस तरह से देखेगा, यह सब कुछ करता है और यह निरंतर तह, प्रतिलिपि प्रचार, सीएसई, आदि कर सकता है। - उसके लिए एक पूरी तरह से अलग तस्वीर खुल जाएगी। LLVM IR और .NET IL एक विशिष्ट प्रोग्रामिंग भाषा से बंधे नहीं हैं, और आप यह सुनिश्चित नहीं कर सकते हैं कि कोई विशिष्ट / नया PL प्रभावी रूप से IR पर ही अनुवाद कर सकता है। ठीक है, क्यों इसके बारे में बात करते हैं यदि आप एक विशिष्ट एप्लिकेशन पर InstCombine के प्रदर्शन का परीक्षण कर सकते हैं और ;-)। यह संभावना नहीं है कि यह एक प्रभावशाली अंतर होगा, लेकिन कौन जानता है।

C # के बारे में क्या?

जैसा कि मैंने कहा, जिन अभिव्यक्तियों की हमने जांच की, उनमें C # अनुपस्थित हैं। लेकिन जब मैं कहता हूं कि C # मेरा मतलब है कि सबसे लोकप्रिय रनटाइम CoreCLR और RyuJIT है। लेकिन कोरसीएलआर के अलावा एलएलवीएम का उपयोग करने वालों में एक बैकेंड के रूप में अन्य रनटाइम शामिल हैं: मोनो (मेरे ट्वीट देखें), यूनिटी बर्स्ट, IL2CPP (क्लैंग के माध्यम से) और LILLC - यहां आप सुरक्षित रूप से क्लैंग के साथ ++ परिणामों की तुलना कर सकते हैं। यूनिटी के लोग C # में आंतरिक C ++ कोड को फिर से लिखते हैं, प्रदर्शन, प्रमाण में किसी भी नुकसान के बिना!

यहां कुछ ऑप्टिमाइज़ेशन पाइपहोल दिए गए हैं जो टिप्पणियों से morph.cpp स्रोत कोड में morph.cpp फ़ाइल में मिल सकते हैं (स्पष्ट रूप से थोड़ा और अधिक हैं):

 *(&X) => X X % 1 => 0 X / 1 => X X % Y => X - (X / Y) * Y X ^ -1 => ~x X >= 1 => X > 0 X < 1 => X <= 0 X + 1 == C2 => X == C2 - C1 ((X + C1) + C2) => (X + (C1 + C2)) ((X + C1) + (Y + C2)) => ((X + Y) + (C1 + C2)) 

कुछ और लोअरिंग.कैप (निम्न-स्तर) में पाए जा सकते हैं, लेकिन सामान्य तौर पर RyuJIT जाहिर तौर पर यहाँ C C ट्रेलरों से हार जाता है। RyuJIT की प्राथमिकताएं थोड़ी अलग हैं - टेरिंग संकलन के आगमन से पहले, उन्हें एक स्वीकार्य संकलन गति प्रदान करने की आवश्यकता थी, जो कि वह C ++ कंपाइलर्स के विपरीत बहुत अच्छी तरह से करता है (एलएलवीएम में 30-लाइन इंस्टाकोम्बिन पास के बारे में याद रखें और सामान्य रूप से दिलचस्प पोस्ट पढ़ें " आधुनिक "सी ++ विलाप ) और कॉल विचलन, मुक्केबाजी और आवंटन (एक ही वस्तु ढेर आवंटन ) के उन्मूलन के क्षेत्र में अनुकूलन विकसित करने के लिए यह बहुत अधिक उपयोगी है - यह सब, जाहिर है, स्पर्श में कोज्या द्वारा साइन के विभाजन को कम करने के लिए बहुत अधिक महत्वपूर्ण है।

शायद टेरिंग संकलन के आगमन के साथ, समय के साथ कई नए अनुकूलन होंगे जो टियर 1 या टियर 2 के संकलन समय के लिए महत्वपूर्ण नहीं हैं। हो सकता है कि आपके ऐड-इन एपीआई और डीएसएल के साथ भी - आपने अभी यह लेख पढ़ा है, इसमें प्रथमेश कुलकर्णी ने जीसीसी में अभिव्यक्ति अनुकूलन को सिर्फ एक-दो डीएसएल लाइनों में जोड़ा है:

 (simplify (plus (mult (SIN @0) (SIN @0)) (mult (COS @0) (COS @0))) (if (flag_unsafe_math_optimizations)1. { build_one_cst (TREE_TYPE (@0)); })) 

एक गणित पाठ्यपुस्तक से इस अभिव्यक्ति के लिए ;-):

 cos^2(X) + sin^2(X) equals to 1 

उपयोगी लिंक

1. "फ्यूचर डायरेक्शन्स फॉर ऑप्टिमाइज़िंग कम्पाइलर्स" , नूनो पी। लोप्स और जॉन रेगेर
2. "एलएलवीएम एक फ़ंक्शन का अनुकूलन कैसे करता है" , जॉन रेगेर
3. "आधुनिक संकलक की आश्चर्यजनक चतुराई" , डैनियल लेमायर
4. "जीसीसी में पीपहोल अनुकूलन को जोड़ना" , प्रथमेश कुलकर्णी
5. 5. "सी ++, सी # और यूनिटी" , लुकास मीजेर
6. "आधुनिक" सी ++ विलाप " , अरास प्राणकेवियस
7. "एलीव के साथ सही ढंग से पीपहोल ऑप्टिमाइज़ेशन" , नूनो पी। लोप्स, डेविड मेनेंडेज़, संतोष नागरकाटे और जॉन रेगर