-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathEdge_Types.html
136 lines (135 loc) · 6.75 KB
/
Edge_Types.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
<?xml version='1.0' encoding='utf-8'?>
<!DOCTYPE html PUBLIC '-//W3C//DTD XHTML 1.0 Transitional//EN' 'http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd'>
<html xmlns='http://www.w3.org/1999/xhtml'>
<head>
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no"/>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<title>Firm - Edge Types</title>
<link rel="stylesheet" type="text/css" href="style.css"/>
<link rel="stylesheet" type="text/css" href="pygments.css"/>
<link rel="icon" type="image/png" href="logo-simple.png"/>
</head>
<body>
<div class="layout-header">
<a href="index.html"><img src="logo.png" alt="Firm Logo" /></a>
</div>
<div class="layout-content-wrapper">
<div class="layout-content">
<div class="layout-sidebar">
<ul>
<li><a href="index.html">About</a></li>
<li><a href="Features.html">Features</a></li>
<li><a href="Download.html">Download</a></li>
<li><a href="Documentation.html">Documentation</a></li>
<li><a href="Projects.html">Projects</a></li>
<li><a href="Development.html">Development</a></li>
<li><a href="Contact.html">Contact</a></li>
</ul>
<ul class="external">
<li><a href="http://pp.info.uni-karlsruhe.de/projects/firm_publications.php">Publications</a></li>
</ul>
<div class="layout-toc">
<h2>Contents</h2>
<ul>
<li><a href="#_forward_edges">Forward Edges</a>
<ul>
<li><a href="#_data_dependencies_black">Data Dependencies (black)</a></li>
<li><a href="#_reversed_control_flow_edges_red">Reversed Control Flow Edges (red)</a>
<ul>
<li><a href="#_special_case_back_edges">Special Case: Back Edges</a></li>
</ul>
</li>
<li><a href="#_memory_dependencies_blue">Memory Dependencies (blue)</a></li>
<li><a href="#_keeps_violet">Keeps (violet)</a></li>
<li><a href="#_other_dependencies_green">Other Dependencies (green)</a></li>
</ul>
</li>
<li><a href="#_reverse_edges">Reverse Edges</a>
<ul>
<li><a href="#_outs">Outs</a></li>
<li><a href="#_out_edges">Out Edges</a></li>
</ul>
</li>
</ul>
</div>
</div>
<div class="layout-document">
<h1>Edge Types</h1>
<div id="preamble">
<div class="sectionbody">
<div class="paragraph"><p>People, who know intermediate representations from text books,
are often confused because <span class="algo">Firm</span> shows edges in the wrong direction.
Instead of data flow, <span class="algo">Firm</span> provides data dependencies,
which is usually more convenient in practice.
So, "forward" means from the End to the Start node.</p></div>
</div>
</div>
<div class="sect1">
<h2 id="_forward_edges">Forward Edges</h2>
<div class="sectionbody">
<div class="sect2">
<h3 id="_data_dependencies_black">Data Dependencies (black)</h3>
<div class="paragraph"><p>These are the most common edges.
An operation is connected with a data dependency to its operands.</p></div>
</div>
<div class="sect2">
<h3 id="_reversed_control_flow_edges_red">Reversed Control Flow Edges (red)</h3>
<div class="paragraph"><p>Reversed, these edges form (sort of) a control flow graph.
However, these edges go to the operation (not the block),
which is used to jump to the source block.</p></div>
<div class="paragraph"><p>These edges are not control dependencies!</p></div>
<div class="sect3">
<h4 id="_special_case_back_edges">Special Case: Back Edges</h4>
<div class="paragraph"><p>A reversed control flow edge, where the block of the target node dominates (or is) the source block.</p></div>
<div class="paragraph"><p>Do not confuse back edges with reversed edges!</p></div>
</div>
</div>
<div class="sect2">
<h3 id="_memory_dependencies_blue">Memory Dependencies (blue)</h3>
<div class="paragraph"><p>Memory dependencies represent a special form of data dependency,
where the value is the memory.
In contrast to other SSA values, memory cannot be duplicated.
Intuitively, a store operation consumes the whole memory state
and produces a new state.</p></div>
</div>
<div class="sect2">
<h3 id="_keeps_violet">Keeps (violet)</h3>
<div class="paragraph"><p>If code is dead, but <a href="Unreachable_Code.html">reachable</a>, e.g. infinite loops,
the keep edges are <span class="algo">Firm</span>’s hack to "keep" the code,
because they provide a path from the End node.</p></div>
</div>
<div class="sect2">
<h3 id="_other_dependencies_green">Other Dependencies (green)</h3>
<div class="paragraph"><p>Additional dependencies with no special semantics.</p></div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_reverse_edges">Reverse Edges</h2>
<div class="sectionbody">
<div class="paragraph"><p>Sometimes it is necessary to walk a <span class="algo">Firm</span> graph in data <em>flow</em> order.
So lib<span class="algo"><span class="algo">Firm</span></span> provides the following mechanisms.</p></div>
<div class="sect2">
<h3 id="_outs">Outs</h3>
<div class="paragraph"><p>Outs are the reversed form of the dependencies above.
However, any change to the graph makes this edges inconsistent,
but the corresponding flag is not set implicitly.</p></div>
</div>
<div class="sect2">
<h3 id="_out_edges">Out Edges</h3>
<div class="paragraph"><p>These are like outs, but are updated automatically.
These automatic updates can be switched on and off (edges_activate, edges_deactivate).
However, keep in mind that this means that dead code does not disappear implicitly,
because it is still referenced by out edges.</p></div>
</div>
</div>
</div>
</div>
<div class="clear"></div>
</div>
</div>
<div class="layout-footer">
<span><a href="https://lists.ira.uni-karlsruhe.de/mailman/listinfo/firm">Mailing list</a>: <a href="mailto:[email protected]">[email protected]</a></span>
</div>
</body>
</html>