Alias-analysis.html 7.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190
  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: Alias analysis</title>
  20. <meta name="description" content="GNU Compiler Collection (GCC) Internals: Alias analysis">
  21. <meta name="keywords" content="GNU Compiler Collection (GCC) Internals: Alias analysis">
  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="Memory-model.html#Memory-model" rel="next" title="Memory model">
  31. <link href="SSA.html#SSA" rel="prev" title="SSA">
  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="Alias-analysis"></a>
  63. <div class="header">
  64. <p>
  65. Next: <a href="Memory-model.html#Memory-model" accesskey="n" rel="next">Memory model</a>, Previous: <a href="SSA.html#SSA" accesskey="p" rel="prev">SSA</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="Alias-analysis-1"></a>
  69. <h3 class="section">12.4 Alias analysis</h3>
  70. <a name="index-alias"></a>
  71. <a name="index-flow_002dsensitive-alias-analysis"></a>
  72. <a name="index-flow_002dinsensitive-alias-analysis"></a>
  73. <p>Alias analysis in GIMPLE SSA form consists of two pieces. First
  74. the virtual SSA web ties conflicting memory accesses and provides
  75. a SSA use-def chain and SSA immediate-use chains for walking
  76. possibly dependent memory accesses. Second an alias-oracle can
  77. be queried to disambiguate explicit and implicit memory references.
  78. </p>
  79. <ol>
  80. <li> Memory SSA form.
  81. <p>All statements that may use memory have exactly one accompanied use of
  82. a virtual SSA name that represents the state of memory at the
  83. given point in the IL.
  84. </p>
  85. <p>All statements that may define memory have exactly one accompanied
  86. definition of a virtual SSA name using the previous state of memory
  87. and defining the new state of memory after the given point in the IL.
  88. </p>
  89. <div class="smallexample">
  90. <pre class="smallexample">int i;
  91. int foo (void)
  92. {
  93. # .MEM_3 = VDEF &lt;.MEM_2(D)&gt;
  94. i = 1;
  95. # VUSE &lt;.MEM_3&gt;
  96. return i;
  97. }
  98. </pre></div>
  99. <p>The virtual SSA names in this case are <code>.MEM_2(D)</code> and
  100. <code>.MEM_3</code>. The store to the global variable <code>i</code>
  101. defines <code>.MEM_3</code> invalidating <code>.MEM_2(D)</code>. The
  102. load from <code>i</code> uses that new state <code>.MEM_3</code>.
  103. </p>
  104. <p>The virtual SSA web serves as constraints to SSA optimizers
  105. preventing illegitimate code-motion and optimization. It
  106. also provides a way to walk related memory statements.
  107. </p>
  108. </li><li> Points-to and escape analysis.
  109. <p>Points-to analysis builds a set of constraints from the GIMPLE
  110. SSA IL representing all pointer operations and facts we do
  111. or do not know about pointers. Solving this set of constraints
  112. yields a conservatively correct solution for each pointer
  113. variable in the program (though we are only interested in
  114. SSA name pointers) as to what it may possibly point to.
  115. </p>
  116. <p>This points-to solution for a given SSA name pointer is stored
  117. in the <code>pt_solution</code> sub-structure of the
  118. <code>SSA_NAME_PTR_INFO</code> record. The following accessor
  119. functions are available:
  120. </p>
  121. <ul>
  122. <li> <code>pt_solution_includes</code>
  123. </li><li> <code>pt_solutions_intersect</code>
  124. </li></ul>
  125. <p>Points-to analysis also computes the solution for two special
  126. set of pointers, <code>ESCAPED</code> and <code>CALLUSED</code>. Those
  127. represent all memory that has escaped the scope of analysis
  128. or that is used by pure or nested const calls.
  129. </p>
  130. </li><li> Type-based alias analysis
  131. <p>Type-based alias analysis is frontend dependent though generic
  132. support is provided by the middle-end in <code>alias.c</code>. TBAA
  133. code is used by both tree optimizers and RTL optimizers.
  134. </p>
  135. <p>Every language that wishes to perform language-specific alias analysis
  136. should define a function that computes, given a <code>tree</code>
  137. node, an alias set for the node. Nodes in different alias sets are not
  138. allowed to alias. For an example, see the C front-end function
  139. <code>c_get_alias_set</code>.
  140. </p>
  141. </li><li> Tree alias-oracle
  142. <p>The tree alias-oracle provides means to disambiguate two memory
  143. references and memory references against statements. The following
  144. queries are available:
  145. </p>
  146. <ul>
  147. <li> <code>refs_may_alias_p</code>
  148. </li><li> <code>ref_maybe_used_by_stmt_p</code>
  149. </li><li> <code>stmt_may_clobber_ref_p</code>
  150. </li></ul>
  151. <p>In addition to those two kind of statement walkers are available
  152. walking statements related to a reference ref.
  153. <code>walk_non_aliased_vuses</code> walks over dominating memory defining
  154. statements and calls back if the statement does not clobber ref
  155. providing the non-aliased VUSE. The walk stops at
  156. the first clobbering statement or if asked to.
  157. <code>walk_aliased_vdefs</code> walks over dominating memory defining
  158. statements and calls back on each statement clobbering ref
  159. providing its aliasing VDEF. The walk stops if asked to.
  160. </p>
  161. </li></ol>
  162. <hr>
  163. <div class="header">
  164. <p>
  165. Next: <a href="Memory-model.html#Memory-model" accesskey="n" rel="next">Memory model</a>, Previous: <a href="SSA.html#SSA" accesskey="p" rel="prev">SSA</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>
  166. </div>
  167. </body>
  168. </html>