Basic blocks, DAGs और safe local optimization
लक्ष्य और semantic assumptions
Basic blocks पहचानें और observable behavior बचाते हुए local rewrites करें। मुख्य उदाहरण में scalar mathematical integers, pure nontrapping arithmetic और कोई pointers, calls, volatile operations या concurrency नहीं हैं। आगे बताएँगे कि ये शर्तें क्यों जरूरी हैं। Optimization में भाषा का behavior बचता है, केवल expression छोटा नहीं होता।
1. Leaders, blocks और CFG
Basic block maximal straight-line sequence है, जिसमें entry केवल पहले instruction पर और exit केवल अंत पर होती है। Leaders: पहला instruction, हर jump target तथा branch के तुरंत बाद वाला instruction, यदि हो। Leaders पर partition करें। CFG edge अगले संभव block तक जाता है; conditional branch में target और fall-through दोनों edges हो सकते हैं। Return का साधारण successor नहीं।
Numbered IR:
1: x=0 2: if p goto 5 3: x=1 4: goto 6 5: x=2 6: y=x+1 7: return y
Leaders 1,3,5,6 हैं; blocks [1,2], [3,4], [5], [6,7] हैं। [1,2] से [5] तथा [3,4] edges हैं; दोनों आगे [6,7] जाते हैं। Line 5 से line 6 fall-through है। केवल label खुद branch नहीं बनाता, मगर वास्तविक jump target नया block शुरू करता है। यहाँ x=0 दोनों paths पर use से पहले overwrite होता है; इसे सिद्ध करने में पहले block से बाहर का context चाहिए।
2. Common expressions और value identities
Block में t1=a+b के बाद t2=a+b पहले result को reuse कर सकता है, जब a,b के values नहीं बदले और operation सुरक्षित हो। DAG node एक operator और खास operand-value nodes दर्शाता है। कई variable names एक node label कर सकते हैं। a=a+1 के बाद a नए value node को दर्शाता है; spelling समान होने पर भी नया a+b अलग value है।
Worked block में exit पर केवल a,t3,out live हैं:
t1=a+b t2=a+b a=a+1 t3=a+b dead=t2*0 out=t1+t2
Incoming values को a0,b0 leaves दें। t1,t2 दोनों plus(a0,b0) share करते हैं। a update से plus(a0,1), यानी a1 बनता है। t3, plus(a1,b0) है; उसे t1 से नहीं बदल सकते। dead का आगे use नहीं और exit पर live नहीं, इसलिए pure computation हटा सकते हैं। t2 के uses को t1 से बदलने पर अलग t2 assignment नहीं चाहिए। सही result: t1=a+b; a=a+1; t3=a+b; out=t1+t1। Incoming a=2,b=5 पर दोनों में a=3,t3=8,out=14 हैं। अनुपयोगी local temporaries की अंतिम values बचाना जरूरी नहीं।
3. Copy propagation, folding और rewrites
Constant folding में t=3*4 से t=12 बनता है। Constant propagation ज्ञात constant variable के uses बदलती है; दोनों अलग reasoning हैं। u=v के बाद u को v से तभी बदलें जब v copied value ही रखता हो। u=v; v=7; w=u+1 में u को नए v से बदलना गलत है, जब तक पुराना v भी 7 होने का अलग प्रमाण न हो।
Strength reduction महँगी operation का सस्ता equivalent देता है, जैसे type और language rules अनुमति दें तो power-of-two multiplication की जगह shift। Mathematical integers में x+0=x, x*1=x सरल हैं, लेकिन हर floating-point, overflow, exception, signed-zero model में इन्हें अंधाधुंध न लगाएँ। Dead-code elimination unused value का assignment हटाती है, बशर्ते evaluation के effects हटाना भी सुरक्षित हो।
4. Aliasing, calls और exceptions
t1=*p; q=7; t2=p में दूसरी load को सामान्यतः t1 से नहीं बदल सकते, क्योंकि p,q alias हो सकते हैं। अलग locations का प्रमाण मिले तो निष्कर्ष बदल सकता है। Call visible memory बदल सकता है; effects न मालूम हों तो memory-based value facts invalidate करने पड़ सकते हैं।
Unused expression भी trap, I/O या volatile update कर सकता है। जहाँ division-by-zero observable है, unused z=1/0 हटाना behavior बदलता है। केवल liveness deletion की अनुमति नहीं देती। मुख्य scalar उदाहरण में traps/effects निषिद्ध थे, इसलिए dead हटाना उचित था। अंतिम scalar value बचाना और पूरा behavior बचाना अलग बातें हैं।
तरीका और सावधानियाँ
पहले assumptions और exit-live variables लिखें। Operand values तथा सभी redefinitions पहचानें। फिर justified rewrites लगाएँ, test trace चलाएँ और सभी legal inputs पर सोचें। Test गलती दिखा सकता है, equivalence सिद्ध नहीं करता। केवल expression spelling से reuse न करें। Current block में पढ़ा न गया output variable आगे live हो सकता है।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें.
P01. Numbered CFG उदाहरण में leaders कौन हैं?
A. {1,2,4} B. {1,3,5,6} C. {1,5} D. हर instruction
उत्तर: B
A: Branch instruction खुद leader होना जरूरी नहीं।
B: First, branch के बाद और targets से 1,3,5,6।
C: Post-branch तथा merge leaders छूटे।
D: Straight-line instructions block share कर सकती हैं।
P02. t1=a+b; a=a+1; t3=a+b के बाद general integer inputs में t3 को t1 से बदल सकते हैं?
A. हमेशा B. Spelling समान होने से C. नहीं, a की value बदल गई D. हाँ, t1 temporary हो तो
उत्तर: C
A: Operand value बदली है।
B: Text समान होना पर्याप्त नहीं।
C: दोनों additions अलग a versions लेते हैं।
D: Temporary नाम operand equality नहीं देता।
P03. Worked optimized block में a=2,b=5 पर out=?
A. 7 B. 8 C. 14 D. 16
उत्तर: C
A: 7 पहला shared sum है।
B: 8 बाद का t3 है।
C: out=t1+t1=7+7=14।
D: इसमें updated sum दो बार लगाया।
P04. Unused assignment हटाने का उचित आधार क्या है?
A. Result dead है और evaluation के जरूरी effects नहीं B. Variable name छोटा है C. हमेशा division होना D. हमेशा block में अंतिम होना
उत्तर: A
A: Value use और effects दोनों देखें।
B: नाम से semantics नहीं बदलती।
C: Division trap कर सकता है।
D: Exit-live values आगे चाहिए हो सकती हैं।
P05. t1=*p; q=7; t2=p में t2 के लिए t1 reuse क्यों unsafe हो सकता है?
A. Pointers हमेशा अलग addresses हैं B. p,q alias हो सकते हैं C. Loads की value नहीं होती D. 7 store नहीं कर सकते
उत्तर: B
A: अलग names का address एक हो सकता है।
B: Store उसी location को बदल सकता है।
C: Load value देता है, मगर यहाँ बदल सकती है।
D: 7 store करना समस्या नहीं, aliasing है।
P06. कौन-सा rewrite constant folding है?
A. t=3*4 से t=12 B. u=v से u का use v करना C. Alias proof के बाद दो loads merge D. Loop unroll करना
उत्तर: A
A: Constant operation compile time पर निकली।
B: यह copy propagation है।
C: यह redundancy elimination है।
D: Unrolling body structure दोहराता है।
स्रोत और सीमा
Official 2026 course के अनुसार विषय का सीमित भाग। 2027 की पूर्णता का दावा नहीं। सभी उदाहरण तथा अभ्यास मौलिक हैं.
प्रगति सहेजने के लिए साइन इन करें। साइन इन