Liveness, available expressions और global CSE
लक्ष्य और conventions
दो set-valued data-flow problems हल करें और उनके अलग directions/merge operators समझें। Variables scalar हैं; arithmetic pure, nontrapping है; aliasing stores/calls नहीं और सभी considered CFG edges reachable हैं। Variable live है यदि किसी संभव continuation में उसकी current value redefinition से पहले उपयोग होगी। Expression available है यदि उस point के हर path पर पहले evaluate हुई और उसके बाद किसी operand को फिर define नहीं किया गया।
1. Liveness: backward may analysis
USE[B] में वे variables हैं जो B में अपनी पहली definition से पहले उपयोग हों। DEF[B] में assigned variables हैं। एक variable दोनों में हो सकता है: x=x+1 पहले incoming x पढ़ता है, फिर outgoing x लिखता है। Branch conditions और return expressions भी uses हैं।
OUT[B]=successors S के IN[S] का union। IN[B]=USE[B] ∪ (OUT[B]−DEF[B])। Union का अर्थ एक possible future-use path भी पर्याप्त है। Exit के बाद values जरूरी न हों तो exit OUT empty है। बाकी sets empty से शुरू कर backward fixed point तक iterate करें। Successor न हो तो union empty है। Interface output variables माँगे तो boundary में उन्हें live रखें, dead न मानें।
Worked loop:
B1: a=1; b=2; goto B2 B2: c=a+b; a=c+1; if a<10 goto B2 else B3 B3: return c
USE1=∅, DEF1={a,b}; USE2={a,b}, DEF2={a,c}; USE3={c}, DEF3=∅। B2 में a=c+1, c पढ़ता है, लेकिन c इसी block में पहले defined है; इसलिए USE2 में c नहीं।
सभी IN/OUT empty से शुरू करें। B3,B2,B1 process करें: IN3={c}; OUT2={c}, IN2={a,b}; OUT1={a,b}, IN1=∅। अगले pass में loop successor जुड़ता है: OUT2=IN2∪IN3={a,b,c}; IN2={a,b} ही। अब stable है; OUT3=∅। B2 के अंदर backward trace में live-after={a,b,c} से शुरू करें। Branch से पहले {a,b,c}; a=c+1 से पहले {b,c}; c=a+b से पहले {a,b}। यह block result से मेल खाता है।
2. Available expressions: forward must analysis
U relevant pure expressions का finite universe है। IN[B]=predecessor OUT sets का intersection; OUT[B]=GEN[B] ∪ (IN[B]−KILL[B])। KILL में B में assigned किसी variable वाले expressions हैं। GEN में block के evaluated expressions हैं जिनके operands evaluation के बाद नहीं बदले, result लेने वाले assignment से भी नहीं। x=x+y में RHS पुराने x से निकलता है, फिर x बदल जाता है; इसलिए current operands वाला x+y exit पर generated-available नहीं होता।
Entry IN=∅ है: कोई expression पहले computed नहीं मानी। सामान्य reachable CFG formulation में बाकी must-analysis facts U से शुरू करके नीचे iterate करें और entry boundary fixed रखें। यह liveness के empty initialization से अलग है। Join intersection में expression हर incoming path पर बची होनी चाहिए। Union केवल एक path का result मानकर गलत replacement कर सकती है।
3. Diamond trace और global CSE
Entry से L,R branches और फिर J join है। U={a+b} लें। L में t1=a+b, R में t2=a+b है और a,b कहीं नहीं बदलते। OUT[L]=OUT[R]={a+b}, इसलिए IN[J]={a+b}। J में t3=a+b value-wise redundant है। लेकिन t1 या t2 अकेला J को dominate करना जरूरी नहीं: R path पर t1 नहीं बना, L पर t2 नहीं। साधारण non-SSA IR में दोनों paths पर fresh temporary t=a+b assign कराकर J में t उपयोग कर सकते हैं। SSA में suitable phi दोनों results merge करती है। Availability हर path पर value होने का प्रमाण है, किसी एक predecessor के temporary को हर path पर उपयोग करने की अनुमति नहीं।
अब R में t2=a+b; a=0 कर दें। a+b evaluate होने के बाद kill होता है, इसलिए OUT[R]=∅। IN[J]={a+b}∩∅=∅। पुरानी availability reasoning से J expression नहीं हटा सकते। किसी एक execution में पुराना a भी zero हो तो भी सभी inputs का proof नहीं बनता।
4. Optimization में उपयोग
Liveness dead assignments तथा register allocation में काम आती है, मगर deletion effects/traps भी बचाए। Available expressions CSE में मदद देती है जब operand identities, operator semantics तथा उपयोग योग्य stored result हों। Constant propagation value facts track करती है, ये sets नहीं। उसकी lattice initialization को इन analyses में मिलाना गलती है।
सावधानियाँ
Block USE में definition से पहले के uses आते हैं, सभी uses नहीं। Liveness backward और successor union है; availability forward और predecessor intersection। Join पर may/must अलग रखें। Loops में स्थिर होने तक दोहराएँ। Dead value से computation harmless सिद्ध नहीं होती; available expression से हर पुराना result variable join पर valid नहीं हो जाता।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें.
P01. B2: c=a+b; a=c+1; if a<10... में USE[B2] क्या है?
A. {a,b,c} B. {c} C. {a,b} D. ∅
उत्तर: C
A: c पहले define होकर फिर use है।
B: Incoming c यहाँ use नहीं।
C: a,b definition से पहले पढ़े हैं, c नहीं।
D: पहला assignment incoming a,b पढ़ता है।
P02. Worked loop के liveness fixed point पर OUT[B2] क्या है?
A. {a,b} B. {c} C. ∅ D. {a,b,c}
उत्तर: D
A: Exit successor को c चाहिए।
B: Loop successor को a,b भी चाहिए।
C: Successors को values चाहिए।
D: IN2={a,b} तथा IN3={c} का union तीनों है।
P03. Available expressions में direction और join क्या हैं?
A. Backward union B. Forward intersection C. Forward union D. Backward intersection
उत्तर: B
A: यह liveness है।
B: हर predecessor path पर expression चाहिए।
C: Must property में एक predecessor काफी नहीं।
D: Availability पुराने evaluations से आगे जाती है।
P04. क्या x=x+y सामान्यतः exit पर x+y को available generate करता है?
A. हाँ, evaluate हुआ है B. नहीं, assignment operand x बदलता है C. हाँ, क्योंकि y नहीं बदला D. केवल x live हो तो
उत्तर: B
A: Result पुराने x से बना, current से नहीं।
B: x update current operands वाला expression invalidate करता है।
C: सभी operands की values बचनी चाहिए।
D: Liveness expression equality सिद्ध नहीं।
P05. Diamond के दोनों paths अलग temporaries में a+b बनाते हैं। Join पर availability अकेली क्या सुनिश्चित करती है?
A. Left का t1 हर path पर defined B. Right का t2 हर path पर defined C. हर path पर value computed है; usable merged result अभी चाहिए D. बिना replacement computation हमेशा हटा सकते हैं
उत्तर: C
A: Right path t1 define नहीं करता।
B: Left path t2 define नहीं करता।
C: Common temporary या merge सही result name देता है।
D: Users को सही result चाहिए।
P06. L.OUT={a+b}, R.OUT=∅ हो तो join पर availability क्या है?
A. {a+b} B. ∅ C. {a,b} D. Union undefined है इसलिए unknown
उत्तर: B
A: Expression दोनों paths पर चाहिए।
B: Intersection empty है।
C: Domain expressions है, variables नहीं।
D: Intersection defined है और empty देता है।
स्रोत और सीमा
Official 2026 course के अनुसार विषय का सीमित भाग। 2027 की पूर्णता का दावा नहीं। सभी उदाहरण तथा अभ्यास मौलिक हैं.
प्रगति सहेजने के लिए साइन इन करें। साइन इन