Constant propagation: data flow और fixed points
लक्ष्य और analysis model
CFG में joins तथा loops पर facts निकालें। यहाँ forward, dense, nonrelational constant propagation है; reachable CFG paths लेते हैं और branch-feasibility pruning नहीं करते। हर variable का fact UNDEF, कोई खास constant c, या NAC (एक ज्ञात constant नहीं) है। UNDEF का अर्थ analysis में अभी defining information नहीं पहुँची; runtime zero या uninitialized variable पढ़ने की अनुमति नहीं। Unknown input parameters entry पर NAC हैं।
Information order में UNDEF हर constant के नीचे और हर constant NAC के नीचे है; अलग constants incomparable हैं। कुछ किताबें lattice drawing तथा meet/join नाम उलटे उपयोग करती हैं। यहाँ ⊔ के नियम: UNDEF⊔v=v; c⊔c=c; c≠d पर c⊔d=NAC; NAC⊔v=NAC। Diagram के अनुमान के बजाय ये equations अपनाएँ।
1. Forward equations और transfer
IN[B] predecessors के OUT facts को variable-wise combine करता है। OUT[B]=F_B(IN[B]), जिसमें assignments execution order में चलते हैं। x=5 incoming x कुछ भी हो, x को 5 करता है। x=y, y का current fact copy करता है। Pure x=y+z में दोनों constants हों तो sum; किसी operand का NAC हो तो इस simple analysis में NAC; अन्यथा UNDEF operand हो तो UNDEF। Unassigned variables के facts बने रहते हैं। Assignment पुराने x fact को overwrite करता है।
Entry boundary में unknown बाहरी values NAC और ज्ञात values constants हैं। बाकी computed facts UNDEF से शुरू होकर स्थिर होने तक बदलते हैं। Block transfer पूरी sequence का है, केवल अंतिम assignment का नहीं। Unreachable blocks को अलग सँभालें: उन्हें हटाएँ या explicit reachability model करें; तभी UNDEF joins को runtime guarantee की तरह पढ़ना उचित होगा।
2. Diamond example
Entry unknown p पर branch करता है। Left में x=4; y=2, right में x=4; y=3। दोनों J पर जाते हैं जहाँ z=x+1; w=y+1 है। दोनों branches संभव हैं और कोई path assignments छोड़कर नहीं आता।
Left OUT: x=4,y=2। Right OUT: x=4,y=3। J पर x=4⊔4=4 तथा y=2⊔3=NAC। इसलिए z=5 और w=NAC। z में x को 4 से बदलें और 4+1 को 5 fold करें। y के लिए किसी एक predecessor का value न चुनें, दोनों का average भी नहीं।
Nonrelational सीमा: Left पर x=1,y=2 और right पर x=2,y=1 हो तो join में x,y दोनों NAC हैं। Simple analysis x+y=3 सिद्ध नहीं कर सकता, जबकि दोनों paths पर sum 3 है। Correlation खोना analysis की सीमा है; यह प्रमाण नहीं कि वास्तविक expression अन्य values लेता है।
3. Loop fixed-point trace
Entry E में x=0, फिर loop H में x=x+1; if x<n goto H else Exit है। n unknown positive integer input है और loop में स्थिर रहता है; x,n mathematical integers हैं, overflow या traps नहीं। H कम-से-कम एक बार चलता है, self-edge बना रहता है। H.IN में E.OUT और H.OUT का join है।
H.OUT[x]=UNDEF से शुरू करें। पहला update: H.IN=0⊔UNDEF=0, इसलिए H.OUT=1। अगला: H.IN=0⊔1=NAC, इसलिए H.OUT=NAC। फिर H.IN=0⊔NAC=NAC और H.OUT=NAC ही। Fixed point आ गया। Exit पर x का fact NAC है; वास्तविक exit value n है, इसलिए अलग positive inputs पर 1,2,3,... हो सकती है। पहले pass पर रुककर loop के बाद x=1 मानना गलत होगा।
Flat lattice में variable UNDEF से constant, फिर NAC तक ऊपर जा सकता है। Finite graph और monotone transfer में fixed point मिलता है। Analysis terminate होने के लिए source loop के iterations bounded होना जरूरी नहीं। Worklist में OUT बदलने पर ही successors फिर देखें, अनावश्यक काम घटता है।
4. Facts का सुरक्षित उपयोग
Conservative analysis में reported constant सभी represented executions पर सही होना चाहिए। NAC का अर्थ इस analysis से constant सिद्ध नहीं, यह नहीं कि हर run में value बदलती ही है। Branch-aware sparse conditional constant propagation executable edges track करके कभी अधिक सटीक होती है; वह यहाँ की dense analysis से अलग है।
Calls, pointer stores तथा volatile reads के effects ठीक सँभालने होंगे; scalar examples उनसे मुक्त हैं। Possible redefinition के पार value न चलाएँ, UNDEF को runtime अर्थ न दें, merge में एक predecessor न चुनें, और convergence से पहले loop analysis न रोकें। अधिक replacements से ज्यादा महत्वपूर्ण soundness है।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें.
P01. दिए join में 4⊔4 क्या है?
A. UNDEF B. 4 C. 8 D. NAC
उत्तर: B
A: दोनों paths जानकारी देते हैं।
B: समान constant बचता है।
C: Facts join arithmetic addition नहीं।
D: समान constants conflict नहीं।
P02. दिए join में 2⊔3 क्या है?
A. 2 B. 3 C. 2.5 D. NAC
उत्तर: D
A: केवल एक path चुनना unsound है।
B: दूसरे path का value अलग है।
C: Join average नहीं।
D: अलग constants से single constant guarantee खोती है।
P03. Diamond में दोनों paths पर x=4, y=2 या 3। z=x+1,w=y+1 के facts?
A. z=5,w=NAC B. z=NAC,w=3 C. z=5,w=4 D. दोनों UNDEF
उत्तर: A
A: x बचता है, y एक constant नहीं।
B: x ज्ञात है, y हमेशा 2 नहीं।
C: w एक path पर 3, दूसरे पर 4 है।
D: Incoming definitions जानकारी देती हैं।
P04. E:x=0; H:x=x+1 तथा self-edge में H.OUT[x] का क्रम?
A. UNDEF→1→NAC B. UNDEF→1→1 C. हमेशा 0→2→4 D. NAC→0→1
उत्तर: A
A: Back-edge 1 और entry 0 IN पर conflict करते हैं।
B: यह अगले update में back edge भूलता है।
C: Abstract lattice values merge करता है, हमेशा simulate नहीं।
D: यह join NAC से ऐसे constants नहीं बनाता।
P05. इस analysis में UNDEF क्या है?
A. Runtime zero B. Uninitialized variable पढ़ने की अनुमति C. अभी defining information analysis point तक नहीं पहुँची D. हर integer निश्चित रूप से देखा गया
उत्तर: C
A: Zero implied नहीं।
B: Analysis initialization भाषा की अनुमति नहीं।
C: यह यहाँ का bottom fact है।
D: NAC भी हर value आने का दावा नहीं करता।
P06. Left x=1,y=2; right x=2,y=1। Join पर nonrelational constant analysis क्या करता है?
A. हमेशा x+y=3 सिद्ध B. दोनों NAC, correlation खोता है C. x=y=1.5 करता है D. CFG reject करता है
उत्तर: B
A: यह simple domain relation नहीं रखता।
B: Individual joins cross-variable fact खोते हैं।
C: Constants का average नहीं होता।
D: CFG valid है, abstraction कम सटीक है।
स्रोत और सीमा
Official 2026 course के अनुसार विषय का सीमित भाग। 2027 की पूर्णता का दावा नहीं। सभी उदाहरण तथा अभ्यास मौलिक हैं.
प्रगति सहेजने के लिए साइन इन करें। साइन इन