{"id":254,"date":"2025-11-22T10:50:10","date_gmt":"2025-11-22T10:50:10","guid":{"rendered":"https:\/\/haco.club\/?p=254"},"modified":"2025-11-22T10:50:10","modified_gmt":"2025-11-22T10:50:10","slug":"control-dependence-graph-and-data-dependence-graph","status":"publish","type":"post","link":"https:\/\/haco.club\/?p=254","title":{"rendered":"Control Dependence Graph and Data Dependence Graph"},"content":{"rendered":"\n

A Control Dependence Graph (CDG)<\/strong> and a Data Dependence Graph (DDG)<\/strong> are essential tools in computer science, particularly in compiler design and program analysis.<\/sup> They represent the dependencies between different parts of a program’s code, but they focus on two distinct types of relationships.<\/p>\n\n\n\n

Control Dependence Graph (CDG)<\/h3>\n\n\n\n

A Control Dependence Graph illustrates how the execution of a statement is controlled by a conditional branching statement.<\/sup> In simpler terms, a statement is control-dependent on a conditional if the outcome of that conditional determines whether the statement will be executed.<\/p>\n\n\n\n

    \n
  • Nodes<\/strong>\u00a0in a CDG represent the statements in a program.<\/li>\n\n\n\n
  • Edges<\/strong>\u00a0represent the control dependencies.\u00a0An edge from node A to node B means that the execution of statement B depends on the outcome of the conditional statement A.<\/li>\n<\/ul>\n\n\n\n

    Consider the following code snippet:<\/p>\n\n\n\n

    if (x > y) {\n  z = x;\n} else {\n  z = y;\n}\nprintf(\"%d\", z);<\/code><\/pre>\n\n\n\n
    In the Control Dependence Graph for this code:<\/p>\n\n\n\n
      \n
    • The statements\u00a0z = x;<\/code>\u00a0and\u00a0z = y;<\/code>\u00a0are both control-dependent on the\u00a0if (x > y)<\/code>\u00a0condition. This is because the\u00a0if<\/code>\u00a0statement’s evaluation to true or false directly dictates which of these two assignment statements will run.<\/li>\n\n\n\n
    • The\u00a0printf(\"%d\", z);<\/code>\u00a0statement is not control-dependent on the\u00a0if<\/code>\u00a0statement because it will execute regardless of the condition’s outcome.<\/li>\n<\/ul>\n\n\n\n
      A CDG essentially maps out the “decision-making” structure of a program.<\/strong><\/p>\n\n\n\n
      \n\n\n\n
      Data Dependence Graph (DDG)<\/h3>\n\n\n\n
      A Data Dependence Graph shows how data flows between statements. It identifies situations where two statements access or modify the same memory location, creating a dependency.<\/p>\n\n\n\n
        \n
      • Nodes<\/strong>\u00a0in a DDG represent the statements.<\/li>\n\n\n\n
      • Edges<\/strong>\u00a0represent the data dependencies, indicating that the order of execution between the connected statements matters for the program’s correctness.<\/li>\n<\/ul>\n\n\n\n
        There are three primary types of data dependencies:<\/p>\n\n\n\n
        1\u3001Flow (True) Dependence (RAW – Read After Write):<\/strong>\u00a0A statement\u00a0S2<\/code>\u00a0is flow-dependent on\u00a0S1<\/code>\u00a0if\u00a0S1<\/code>\u00a0writes to a variable that\u00a0S2<\/code>\u00a0later reads.\u00a0The value produced by\u00a0S1<\/code>\u00a0is consumed by\u00a0S2<\/code>.<\/p>\n\n\n\n
        x = 10;  \/\/ S1\ny = x;   \/\/ S2<\/code><\/pre>\n\n\n\n
        Here,\u00a0S2<\/code>\u00a0is flow-dependent on\u00a0S1<\/code>\u00a0because it reads the value of\u00a0x<\/code>\u00a0written by\u00a0S1<\/code>.<\/p>\n\n\n\n
        2\u3001Anti-Dependence (WAR – Write After Read):<\/strong>\u00a0A statement\u00a0S2<\/code>\u00a0is anti-dependent on\u00a0S1<\/code>\u00a0if\u00a0S1<\/code>\u00a0reads a variable that\u00a0S2<\/code>\u00a0later writes to. Reordering these could cause\u00a0S1<\/code>\u00a0to read the wrong value.<\/p>\n\n\n\n
        y = x;   \/\/ S1\nx = 20;  \/\/ S2<\/code><\/pre>\n\n\n\n
        Here,\u00a0S2<\/code>\u00a0is anti-dependent on\u00a0S1<\/code>. If they were swapped,\u00a0S1<\/code>\u00a0would incorrectly use the value\u00a020<\/code>\u00a0for\u00a0x<\/code>.<\/p>\n\n\n\n
        3\u3001Output Dependence (WAW – Write After Write):<\/strong>\u00a0A statement\u00a0S2<\/code>\u00a0is output-dependent on\u00a0S1<\/code>\u00a0if both statements write to the same variable.\u00a0Their relative order must be preserved.<\/p>\n\n\n\n
        x = 10;  \/\/ S1\nx = 20;  \/\/ S2<\/code><\/pre>\n\n\n\n
        Here,\u00a0S2<\/code>\u00a0is output-dependent on\u00a0S1<\/code>. Swapping them would change the final value of\u00a0x<\/code>.<\/p>\n\n\n\n
          <\/ol>\n\n\n\n
          A DDG is crucial for understanding how data is produced and consumed throughout a program.<\/strong><\/p>\n\n\n\n
          \n\n\n\n
          Key Differences Summarized<\/h3>\n\n\n\n
          Feature<\/td>Control Dependence Graph (CDG)<\/td>Data Dependence Graph (DDG)<\/td><\/tr><\/thead>
          Focus<\/strong><\/td>Represents the control flow and decision-making structure.<\/td>Represents the flow of data and dependencies on shared memory locations.<\/td><\/tr>
          Dependency<\/strong><\/td>Based on conditional branches (e.g., if<\/code>, while<\/code>).<\/td>Based on access to the same variable (read\/write operations).<\/td><\/tr>
          Question Answered<\/strong><\/td>“Does the outcome of a conditional statement determine if this statement executes?”<\/td>“Does this statement use, overwrite, or depend on data from another statement?”<\/td><\/tr>
          Primary Use<\/strong><\/td>Program slicing, software testing, and understanding program structure.<\/td>Instruction scheduling, parallelization, and compiler optimizations.<\/td><\/tr><\/tbody><\/table><\/figure>\n","protected":false},"excerpt":{"rendered":"
          A Control Dependence Graph (CDG) and a Data Dependence Graph (DDG) are essential tools […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[42],"tags":[43,44],"class_list":["post-254","post","type-post","status-publish","format-standard","hentry","category-knowledge-base","tag-cdg","tag-ddg"],"_links":{"self":[{"href":"https:\/\/haco.club\/index.php?rest_route=\/wp\/v2\/posts\/254","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/haco.club\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/haco.club\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/haco.club\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/haco.club\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=254"}],"version-history":[{"count":1,"href":"https:\/\/haco.club\/index.php?rest_route=\/wp\/v2\/posts\/254\/revisions"}],"predecessor-version":[{"id":255,"href":"https:\/\/haco.club\/index.php?rest_route=\/wp\/v2\/posts\/254\/revisions\/255"}],"wp:attachment":[{"href":"https:\/\/haco.club\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=254"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haco.club\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=254"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haco.club\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=254"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}