Scalar-evolutions.html 7.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151
  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: Scalar evolutions</title>
  20. <meta name="description" content="GNU Compiler Collection (GCC) Internals: Scalar evolutions">
  21. <meta name="keywords" content="GNU Compiler Collection (GCC) Internals: Scalar evolutions">
  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="Loop-Analysis-and-Representation.html#Loop-Analysis-and-Representation" rel="up" title="Loop Analysis and Representation">
  30. <link href="loop_002div.html#loop_002div" rel="next" title="loop-iv">
  31. <link href="LCSSA.html#LCSSA" rel="prev" title="LCSSA">
  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="Scalar-evolutions"></a>
  63. <div class="header">
  64. <p>
  65. Next: <a href="loop_002div.html#loop_002div" accesskey="n" rel="next">loop-iv</a>, Previous: <a href="LCSSA.html#LCSSA" accesskey="p" rel="prev">LCSSA</a>, Up: <a href="Loop-Analysis-and-Representation.html#Loop-Analysis-and-Representation" accesskey="u" rel="up">Loop Analysis and Representation</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="Scalar-evolutions-1"></a>
  69. <h3 class="section">15.5 Scalar evolutions</h3>
  70. <a name="index-Scalar-evolutions"></a>
  71. <a name="index-IV-analysis-on-GIMPLE"></a>
  72. <p>Scalar evolutions (SCEV) are used to represent results of induction
  73. variable analysis on GIMPLE. They enable us to represent variables with
  74. complicated behavior in a simple and consistent way (we only use it to
  75. express values of polynomial induction variables, but it is possible to
  76. extend it). The interfaces to SCEV analysis are declared in
  77. <samp>tree-scalar-evolution.h</samp>. To use scalar evolutions analysis,
  78. <code>scev_initialize</code> must be used. To stop using SCEV,
  79. <code>scev_finalize</code> should be used. SCEV analysis caches results in
  80. order to save time and memory. This cache however is made invalid by
  81. most of the loop transformations, including removal of code. If such a
  82. transformation is performed, <code>scev_reset</code> must be called to clean
  83. the caches.
  84. </p>
  85. <p>Given an SSA name, its behavior in loops can be analyzed using the
  86. <code>analyze_scalar_evolution</code> function. The returned SCEV however
  87. does not have to be fully analyzed and it may contain references to
  88. other SSA names defined in the loop. To resolve these (potentially
  89. recursive) references, <code>instantiate_parameters</code> or
  90. <code>resolve_mixers</code> functions must be used.
  91. <code>instantiate_parameters</code> is useful when you use the results of SCEV
  92. only for some analysis, and when you work with whole nest of loops at
  93. once. It will try replacing all SSA names by their SCEV in all loops,
  94. including the super-loops of the current loop, thus providing a complete
  95. information about the behavior of the variable in the loop nest.
  96. <code>resolve_mixers</code> is useful if you work with only one loop at a
  97. time, and if you possibly need to create code based on the value of the
  98. induction variable. It will only resolve the SSA names defined in the
  99. current loop, leaving the SSA names defined outside unchanged, even if
  100. their evolution in the outer loops is known.
  101. </p>
  102. <p>The SCEV is a normal tree expression, except for the fact that it may
  103. contain several special tree nodes. One of them is
  104. <code>SCEV_NOT_KNOWN</code>, used for SSA names whose value cannot be
  105. expressed. The other one is <code>POLYNOMIAL_CHREC</code>. Polynomial chrec
  106. has three arguments &ndash; base, step and loop (both base and step may
  107. contain further polynomial chrecs). Type of the expression and of base
  108. and step must be the same. A variable has evolution
  109. <code>POLYNOMIAL_CHREC(base, step, loop)</code> if it is (in the specified
  110. loop) equivalent to <code>x_1</code> in the following example
  111. </p>
  112. <div class="smallexample">
  113. <pre class="smallexample">while (&hellip;)
  114. {
  115. x_1 = phi (base, x_2);
  116. x_2 = x_1 + step;
  117. }
  118. </pre></div>
  119. <p>Note that this includes the language restrictions on the operations.
  120. For example, if we compile C code and <code>x</code> has signed type, then the
  121. overflow in addition would cause undefined behavior, and we may assume
  122. that this does not happen. Hence, the value with this SCEV cannot
  123. overflow (which restricts the number of iterations of such a loop).
  124. </p>
  125. <p>In many cases, one wants to restrict the attention just to affine
  126. induction variables. In this case, the extra expressive power of SCEV
  127. is not useful, and may complicate the optimizations. In this case,
  128. <code>simple_iv</code> function may be used to analyze a value &ndash; the result
  129. is a loop-invariant base and step.
  130. </p>
  131. <hr>
  132. <div class="header">
  133. <p>
  134. Next: <a href="loop_002div.html#loop_002div" accesskey="n" rel="next">loop-iv</a>, Previous: <a href="LCSSA.html#LCSSA" accesskey="p" rel="prev">LCSSA</a>, Up: <a href="Loop-Analysis-and-Representation.html#Loop-Analysis-and-Representation" accesskey="u" rel="up">Loop Analysis and Representation</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>
  135. </div>
  136. </body>
  137. </html>