SSA.html 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353
  1. <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
  2. <html>
  3. <!-- Copyright (C) 1988-2017 Free Software Foundation, Inc.
  4. Permission is granted to copy, distribute and/or modify this document
  5. under the terms of the GNU Free Documentation License, Version 1.3 or
  6. any later version published by the Free Software Foundation; with the
  7. Invariant Sections being "Funding Free Software", the Front-Cover
  8. Texts being (a) (see below), and with the Back-Cover Texts being (b)
  9. (see below). A copy of the license is included in the section entitled
  10. "GNU Free Documentation License".
  11. (a) The FSF's Front-Cover Text is:
  12. A GNU Manual
  13. (b) The FSF's Back-Cover Text is:
  14. You have freedom to copy and modify this GNU Manual, like GNU
  15. software. Copies published by the Free Software Foundation raise
  16. funds for GNU development. -->
  17. <!-- Created by GNU Texinfo 5.2, http://www.gnu.org/software/texinfo/ -->
  18. <head>
  19. <title>GNU Compiler Collection (GCC) Internals: SSA</title>
  20. <meta name="description" content="GNU Compiler Collection (GCC) Internals: SSA">
  21. <meta name="keywords" content="GNU Compiler Collection (GCC) Internals: SSA">
  22. <meta name="resource-type" content="document">
  23. <meta name="distribution" content="global">
  24. <meta name="Generator" content="makeinfo">
  25. <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
  26. <link href="index.html#Top" rel="start" title="Top">
  27. <link href="Option-Index.html#Option-Index" rel="index" title="Option Index">
  28. <link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
  29. <link href="Tree-SSA.html#Tree-SSA" rel="up" title="Tree SSA">
  30. <link href="Alias-analysis.html#Alias-analysis" rel="next" title="Alias analysis">
  31. <link href="SSA-Operands.html#SSA-Operands" rel="prev" title="SSA Operands">
  32. <style type="text/css">
  33. <!--
  34. a.summary-letter {text-decoration: none}
  35. blockquote.smallquotation {font-size: smaller}
  36. div.display {margin-left: 3.2em}
  37. div.example {margin-left: 3.2em}
  38. div.indentedblock {margin-left: 3.2em}
  39. div.lisp {margin-left: 3.2em}
  40. div.smalldisplay {margin-left: 3.2em}
  41. div.smallexample {margin-left: 3.2em}
  42. div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
  43. div.smalllisp {margin-left: 3.2em}
  44. kbd {font-style:oblique}
  45. pre.display {font-family: inherit}
  46. pre.format {font-family: inherit}
  47. pre.menu-comment {font-family: serif}
  48. pre.menu-preformatted {font-family: serif}
  49. pre.smalldisplay {font-family: inherit; font-size: smaller}
  50. pre.smallexample {font-size: smaller}
  51. pre.smallformat {font-family: inherit; font-size: smaller}
  52. pre.smalllisp {font-size: smaller}
  53. span.nocodebreak {white-space:nowrap}
  54. span.nolinebreak {white-space:nowrap}
  55. span.roman {font-family:serif; font-weight:normal}
  56. span.sansserif {font-family:sans-serif; font-weight:normal}
  57. ul.no-bullet {list-style: none}
  58. -->
  59. </style>
  60. </head>
  61. <body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
  62. <a name="SSA"></a>
  63. <div class="header">
  64. <p>
  65. Next: <a href="Alias-analysis.html#Alias-analysis" accesskey="n" rel="next">Alias analysis</a>, Previous: <a href="SSA-Operands.html#SSA-Operands" accesskey="p" rel="prev">SSA Operands</a>, Up: <a href="Tree-SSA.html#Tree-SSA" accesskey="u" rel="up">Tree SSA</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Option-Index.html#Option-Index" title="Index" rel="index">Index</a>]</p>
  66. </div>
  67. <hr>
  68. <a name="Static-Single-Assignment"></a>
  69. <h3 class="section">12.3 Static Single Assignment</h3>
  70. <a name="index-SSA"></a>
  71. <a name="index-static-single-assignment"></a>
  72. <p>Most of the tree optimizers rely on the data flow information provided
  73. by the Static Single Assignment (SSA) form. We implement the SSA form
  74. as described in <cite>R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and
  75. K. Zadeck. Efficiently Computing Static Single Assignment Form and the
  76. Control Dependence Graph. ACM Transactions on Programming Languages
  77. and Systems, 13(4):451-490, October 1991</cite>.
  78. </p>
  79. <p>The SSA form is based on the premise that program variables are
  80. assigned in exactly one location in the program. Multiple assignments
  81. to the same variable create new versions of that variable. Naturally,
  82. actual programs are seldom in SSA form initially because variables
  83. tend to be assigned multiple times. The compiler modifies the program
  84. representation so that every time a variable is assigned in the code,
  85. a new version of the variable is created. Different versions of the
  86. same variable are distinguished by subscripting the variable name with
  87. its version number. Variables used in the right-hand side of
  88. expressions are renamed so that their version number matches that of
  89. the most recent assignment.
  90. </p>
  91. <p>We represent variable versions using <code>SSA_NAME</code> nodes. The
  92. renaming process in <samp>tree-ssa.c</samp> wraps every real and
  93. virtual operand with an <code>SSA_NAME</code> node which contains
  94. the version number and the statement that created the
  95. <code>SSA_NAME</code>. Only definitions and virtual definitions may
  96. create new <code>SSA_NAME</code> nodes.
  97. </p>
  98. <a name="index-PHI-nodes"></a>
  99. <p>Sometimes, flow of control makes it impossible to determine the
  100. most recent version of a variable. In these cases, the compiler
  101. inserts an artificial definition for that variable called
  102. <em>PHI function</em> or <em>PHI node</em>. This new definition merges
  103. all the incoming versions of the variable to create a new name
  104. for it. For instance,
  105. </p>
  106. <div class="smallexample">
  107. <pre class="smallexample">if (&hellip;)
  108. a_1 = 5;
  109. else if (&hellip;)
  110. a_2 = 2;
  111. else
  112. a_3 = 13;
  113. # a_4 = PHI &lt;a_1, a_2, a_3&gt;
  114. return a_4;
  115. </pre></div>
  116. <p>Since it is not possible to determine which of the three branches
  117. will be taken at runtime, we don&rsquo;t know which of <code>a_1</code>,
  118. <code>a_2</code> or <code>a_3</code> to use at the return statement. So, the
  119. SSA renamer creates a new version <code>a_4</code> which is assigned
  120. the result of &ldquo;merging&rdquo; <code>a_1</code>, <code>a_2</code> and <code>a_3</code>.
  121. Hence, PHI nodes mean &ldquo;one of these operands. I don&rsquo;t know
  122. which&rdquo;.
  123. </p>
  124. <p>The following functions can be used to examine PHI nodes
  125. </p>
  126. <dl>
  127. <dt><a name="index-gimple_005fphi_005fresult-1"></a>Function: <strong>gimple_phi_result</strong> <em>(<var>phi</var>)</em></dt>
  128. <dd><p>Returns the <code>SSA_NAME</code> created by PHI node <var>phi</var> (i.e.,
  129. <var>phi</var>&rsquo;s LHS).
  130. </p></dd></dl>
  131. <dl>
  132. <dt><a name="index-gimple_005fphi_005fnum_005fargs-1"></a>Function: <strong>gimple_phi_num_args</strong> <em>(<var>phi</var>)</em></dt>
  133. <dd><p>Returns the number of arguments in <var>phi</var>. This number is exactly
  134. the number of incoming edges to the basic block holding <var>phi</var>.
  135. </p></dd></dl>
  136. <dl>
  137. <dt><a name="index-gimple_005fphi_005farg-1"></a>Function: <strong>gimple_phi_arg</strong> <em>(<var>phi</var>, <var>i</var>)</em></dt>
  138. <dd><p>Returns <var>i</var>th argument of <var>phi</var>.
  139. </p></dd></dl>
  140. <dl>
  141. <dt><a name="index-gimple_005fphi_005farg_005fedge"></a>Function: <strong>gimple_phi_arg_edge</strong> <em>(<var>phi</var>, <var>i</var>)</em></dt>
  142. <dd><p>Returns the incoming edge for the <var>i</var>th argument of <var>phi</var>.
  143. </p></dd></dl>
  144. <dl>
  145. <dt><a name="index-gimple_005fphi_005farg_005fdef"></a>Function: <strong>gimple_phi_arg_def</strong> <em>(<var>phi</var>, <var>i</var>)</em></dt>
  146. <dd><p>Returns the <code>SSA_NAME</code> for the <var>i</var>th argument of <var>phi</var>.
  147. </p></dd></dl>
  148. <a name="Preserving-the-SSA-form"></a>
  149. <h4 class="subsection">12.3.1 Preserving the SSA form</h4>
  150. <a name="index-update_005fssa"></a>
  151. <a name="index-preserving-SSA-form"></a>
  152. <p>Some optimization passes make changes to the function that
  153. invalidate the SSA property. This can happen when a pass has
  154. added new symbols or changed the program so that variables that
  155. were previously aliased aren&rsquo;t anymore. Whenever something like this
  156. happens, the affected symbols must be renamed into SSA form again.
  157. Transformations that emit new code or replicate existing statements
  158. will also need to update the SSA form.
  159. </p>
  160. <p>Since GCC implements two different SSA forms for register and virtual
  161. variables, keeping the SSA form up to date depends on whether you are
  162. updating register or virtual names. In both cases, the general idea
  163. behind incremental SSA updates is similar: when new SSA names are
  164. created, they typically are meant to replace other existing names in
  165. the program.
  166. </p>
  167. <p>For instance, given the following code:
  168. </p>
  169. <div class="smallexample">
  170. <pre class="smallexample"> 1 L0:
  171. 2 x_1 = PHI (0, x_5)
  172. 3 if (x_1 &lt; 10)
  173. 4 if (x_1 &gt; 7)
  174. 5 y_2 = 0
  175. 6 else
  176. 7 y_3 = x_1 + x_7
  177. 8 endif
  178. 9 x_5 = x_1 + 1
  179. 10 goto L0;
  180. 11 endif
  181. </pre></div>
  182. <p>Suppose that we insert new names <code>x_10</code> and <code>x_11</code> (lines
  183. <code>4</code> and <code>8</code>).
  184. </p>
  185. <div class="smallexample">
  186. <pre class="smallexample"> 1 L0:
  187. 2 x_1 = PHI (0, x_5)
  188. 3 if (x_1 &lt; 10)
  189. 4 x_10 = &hellip;
  190. 5 if (x_1 &gt; 7)
  191. 6 y_2 = 0
  192. 7 else
  193. 8 x_11 = &hellip;
  194. 9 y_3 = x_1 + x_7
  195. 10 endif
  196. 11 x_5 = x_1 + 1
  197. 12 goto L0;
  198. 13 endif
  199. </pre></div>
  200. <p>We want to replace all the uses of <code>x_1</code> with the new definitions
  201. of <code>x_10</code> and <code>x_11</code>. Note that the only uses that should
  202. be replaced are those at lines <code>5</code>, <code>9</code> and <code>11</code>.
  203. Also, the use of <code>x_7</code> at line <code>9</code> should <em>not</em> be
  204. replaced (this is why we cannot just mark symbol <code>x</code> for
  205. renaming).
  206. </p>
  207. <p>Additionally, we may need to insert a PHI node at line <code>11</code>
  208. because that is a merge point for <code>x_10</code> and <code>x_11</code>. So the
  209. use of <code>x_1</code> at line <code>11</code> will be replaced with the new PHI
  210. node. The insertion of PHI nodes is optional. They are not strictly
  211. necessary to preserve the SSA form, and depending on what the caller
  212. inserted, they may not even be useful for the optimizers.
  213. </p>
  214. <p>Updating the SSA form is a two step process. First, the pass has to
  215. identify which names need to be updated and/or which symbols need to
  216. be renamed into SSA form for the first time. When new names are
  217. introduced to replace existing names in the program, the mapping
  218. between the old and the new names are registered by calling
  219. <code>register_new_name_mapping</code> (note that if your pass creates new
  220. code by duplicating basic blocks, the call to <code>tree_duplicate_bb</code>
  221. will set up the necessary mappings automatically).
  222. </p>
  223. <p>After the replacement mappings have been registered and new symbols
  224. marked for renaming, a call to <code>update_ssa</code> makes the registered
  225. changes. This can be done with an explicit call or by creating
  226. <code>TODO</code> flags in the <code>tree_opt_pass</code> structure for your pass.
  227. There are several <code>TODO</code> flags that control the behavior of
  228. <code>update_ssa</code>:
  229. </p>
  230. <ul>
  231. <li> <code>TODO_update_ssa</code>. Update the SSA form inserting PHI nodes
  232. for newly exposed symbols and virtual names marked for updating.
  233. When updating real names, only insert PHI nodes for a real name
  234. <code>O_j</code> in blocks reached by all the new and old definitions for
  235. <code>O_j</code>. If the iterated dominance frontier for <code>O_j</code>
  236. is not pruned, we may end up inserting PHI nodes in blocks that
  237. have one or more edges with no incoming definition for
  238. <code>O_j</code>. This would lead to uninitialized warnings for
  239. <code>O_j</code>&rsquo;s symbol.
  240. </li><li> <code>TODO_update_ssa_no_phi</code>. Update the SSA form without
  241. inserting any new PHI nodes at all. This is used by passes that
  242. have either inserted all the PHI nodes themselves or passes that
  243. need only to patch use-def and def-def chains for virtuals
  244. (e.g., DCE).
  245. </li><li> <code>TODO_update_ssa_full_phi</code>. Insert PHI nodes everywhere
  246. they are needed. No pruning of the IDF is done. This is used
  247. by passes that need the PHI nodes for <code>O_j</code> even if it
  248. means that some arguments will come from the default definition
  249. of <code>O_j</code>&rsquo;s symbol (e.g., <code>pass_linear_transform</code>).
  250. <p>WARNING: If you need to use this flag, chances are that your
  251. pass may be doing something wrong. Inserting PHI nodes for an
  252. old name where not all edges carry a new replacement may lead to
  253. silent codegen errors or spurious uninitialized warnings.
  254. </p>
  255. </li><li> <code>TODO_update_ssa_only_virtuals</code>. Passes that update the
  256. SSA form on their own may want to delegate the updating of
  257. virtual names to the generic updater. Since FUD chains are
  258. easier to maintain, this simplifies the work they need to do.
  259. NOTE: If this flag is used, any OLD-&gt;NEW mappings for real names
  260. are explicitly destroyed and only the symbols marked for
  261. renaming are processed.
  262. </li></ul>
  263. <a name="Examining-SSA_005fNAME-nodes"></a>
  264. <h4 class="subsection">12.3.2 Examining <code>SSA_NAME</code> nodes</h4>
  265. <a name="index-examining-SSA_005fNAMEs"></a>
  266. <p>The following macros can be used to examine <code>SSA_NAME</code> nodes
  267. </p>
  268. <dl>
  269. <dt><a name="index-SSA_005fNAME_005fDEF_005fSTMT"></a>Macro: <strong>SSA_NAME_DEF_STMT</strong> <em>(<var>var</var>)</em></dt>
  270. <dd><p>Returns the statement <var>s</var> that creates the <code>SSA_NAME</code>
  271. <var>var</var>. If <var>s</var> is an empty statement (i.e., <code>IS_EMPTY_STMT
  272. (<var>s</var>)</code> returns <code>true</code>), it means that the first reference to
  273. this variable is a USE or a VUSE.
  274. </p></dd></dl>
  275. <dl>
  276. <dt><a name="index-SSA_005fNAME_005fVERSION"></a>Macro: <strong>SSA_NAME_VERSION</strong> <em>(<var>var</var>)</em></dt>
  277. <dd><p>Returns the version number of the <code>SSA_NAME</code> object <var>var</var>.
  278. </p></dd></dl>
  279. <a name="Walking-the-dominator-tree"></a>
  280. <h4 class="subsection">12.3.3 Walking the dominator tree</h4>
  281. <dl>
  282. <dt><a name="index-walk_005fdominator_005ftree"></a>Tree SSA function: <em>void</em> <strong>walk_dominator_tree</strong> <em>(<var>walk_data</var>, <var>bb</var>)</em></dt>
  283. <dd>
  284. <p>This function walks the dominator tree for the current CFG calling a
  285. set of callback functions defined in <var>struct dom_walk_data</var> in
  286. <samp>domwalk.h</samp>. The call back functions you need to define give you
  287. hooks to execute custom code at various points during traversal:
  288. </p>
  289. <ol>
  290. <li> Once to initialize any local data needed while processing
  291. <var>bb</var> and its children. This local data is pushed into an
  292. internal stack which is automatically pushed and popped as the
  293. walker traverses the dominator tree.
  294. </li><li> Once before traversing all the statements in the <var>bb</var>.
  295. </li><li> Once for every statement inside <var>bb</var>.
  296. </li><li> Once after traversing all the statements and before recursing
  297. into <var>bb</var>&rsquo;s dominator children.
  298. </li><li> It then recurses into all the dominator children of <var>bb</var>.
  299. </li><li> After recursing into all the dominator children of <var>bb</var> it
  300. can, optionally, traverse every statement in <var>bb</var> again
  301. (i.e., repeating steps 2 and 3).
  302. </li><li> Once after walking the statements in <var>bb</var> and <var>bb</var>&rsquo;s
  303. dominator children. At this stage, the block local data stack
  304. is popped.
  305. </li></ol>
  306. </dd></dl>
  307. <hr>
  308. <div class="header">
  309. <p>
  310. Next: <a href="Alias-analysis.html#Alias-analysis" accesskey="n" rel="next">Alias analysis</a>, Previous: <a href="SSA-Operands.html#SSA-Operands" accesskey="p" rel="prev">SSA Operands</a>, Up: <a href="Tree-SSA.html#Tree-SSA" accesskey="u" rel="up">Tree SSA</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Option-Index.html#Option-Index" title="Index" rel="index">Index</a>]</p>
  311. </div>
  312. </body>
  313. </html>