DAG (Directed Acyclic Graph) Representation क्या है?

Compiler Design में DAG (Directed Acyclic Graph) Representation एक तकनीक है, जिसका उपयोग Basic Blocks के अंदर उप-अभिव्यक्तियों (Sub-expressions) को साझा करने और कोड ऑप्टिमाइज़ेशन करने के लिए किया जाता है। यह एक गैर-दोहराव (Non-redundant) डेटा संरचना है, जो गणना को अधिक प्रभावी बनाती है।

DAG Representation की विशेषताएँ

• DAG एक **Directed Acyclic Graph** होता है, जिसमें कोई **साइकिल (Cycle)** नहीं होती।
• यह **कॉमन सब-एक्सप्रेशन्स** को पहचानता है और **Duplicate Computation** को हटाता है।
• यह **Basic Blocks** के अंदर **Expression Optimization** में मदद करता है।

Basic Blocks के लिए DAG Representation कैसे बनता है?

किसी भी Basic Block के लिए DAG Representation बनाने के लिए निम्नलिखित चरण होते हैं:

1. सभी वेरिएबल्स और उनके ऑपरेशन्स के लिए नोड्स बनाएं।
2. समान सब-एक्सप्रेशन्स को मर्ज करें।
3. Expression Tree का उपयोग करके DAG बनाएं।

Example:

मान लीजिए हमारे पास निम्नलिखित Basic Block है:

t1 = a + b;
t2 = t1 * c;
t3 = a + b;
t4 = t3 * d;
t5 = t2 + t4;

इसका DAG Representation:

        +
      /     
     a     b
     |     |
     *     *
     |     |
     c     d
         /
        +

DAG Representation के लाभ

लाभ	विवरण
Common Subexpression Elimination	एक्सप्रेशन्स के पुन: उपयोग के द्वारा **Redundant Computation** को हटाता है।
Constant Folding	स्थिर (Constant) मानों के लिए गणना को संकलन (Compile-Time) पर निष्पादित करता है।
Dead Code Elimination	अनावश्यक गणनाओं को हटाकर कोड को छोटा और कुशल बनाता है।

DAG Representation और Three-Address Code

Three-Address Code (TAC) को भी DAG से बेहतर बनाया जा सकता है।

उदाहरण:

Without DAG:
t1 = a + b;
t2 = t1 * c;
t3 = a + b;
t4 = t3 * d;
t5 = t2 + t4;

With DAG:
t1 = a + b;
t2 = t1 * c;
t4 = t1 * d;
t5 = t2 + t4;

निष्कर्ष

DAG Representation कंपाइलर डिजाइन में **Code Optimization** का एक महत्वपूर्ण हिस्सा है। यह **Common Subexpression Elimination, Dead Code Elimination**, और **Constant Folding** जैसी तकनीकों के माध्यम से कंपाइलर को अधिक प्रभावी बनाता है।