Number-of-iterations.html 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164
  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: Number of iterations</title>
  20. <meta name="description" content="GNU Compiler Collection (GCC) Internals: Number of iterations">
  21. <meta name="keywords" content="GNU Compiler Collection (GCC) Internals: Number of iterations">
  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="Dependency-analysis.html#Dependency-analysis" rel="next" title="Dependency analysis">
  31. <link href="loop_002div.html#loop_002div" rel="prev" title="loop-iv">
  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="Number-of-iterations"></a>
  63. <div class="header">
  64. <p>
  65. Next: <a href="Dependency-analysis.html#Dependency-analysis" accesskey="n" rel="next">Dependency analysis</a>, Previous: <a href="loop_002div.html#loop_002div" accesskey="p" rel="prev">loop-iv</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="Number-of-iterations-analysis"></a>
  69. <h3 class="section">15.7 Number of iterations analysis</h3>
  70. <a name="index-Number-of-iterations-analysis"></a>
  71. <p>Both on GIMPLE and on RTL, there are functions available to determine
  72. the number of iterations of a loop, with a similar interface. The
  73. number of iterations of a loop in GCC is defined as the number of
  74. executions of the loop latch. In many cases, it is not possible to
  75. determine the number of iterations unconditionally &ndash; the determined
  76. number is correct only if some assumptions are satisfied. The analysis
  77. tries to verify these conditions using the information contained in the
  78. program; if it fails, the conditions are returned together with the
  79. result. The following information and conditions are provided by the
  80. analysis:
  81. </p>
  82. <ul>
  83. <li> <code>assumptions</code>: If this condition is false, the rest of
  84. the information is invalid.
  85. </li><li> <code>noloop_assumptions</code> on RTL, <code>may_be_zero</code> on GIMPLE: If
  86. this condition is true, the loop exits in the first iteration.
  87. </li><li> <code>infinite</code>: If this condition is true, the loop is infinite.
  88. This condition is only available on RTL. On GIMPLE, conditions for
  89. finiteness of the loop are included in <code>assumptions</code>.
  90. </li><li> <code>niter_expr</code> on RTL, <code>niter</code> on GIMPLE: The expression
  91. that gives number of iterations. The number of iterations is defined as
  92. the number of executions of the loop latch.
  93. </li></ul>
  94. <p>Both on GIMPLE and on RTL, it necessary for the induction variable
  95. analysis framework to be initialized (SCEV on GIMPLE, loop-iv on RTL).
  96. On GIMPLE, the results are stored to <code>struct tree_niter_desc</code>
  97. structure. Number of iterations before the loop is exited through a
  98. given exit can be determined using <code>number_of_iterations_exit</code>
  99. function. On RTL, the results are returned in <code>struct niter_desc</code>
  100. structure. The corresponding function is named
  101. <code>check_simple_exit</code>. There are also functions that pass through
  102. all the exits of a loop and try to find one with easy to determine
  103. number of iterations &ndash; <code>find_loop_niter</code> on GIMPLE and
  104. <code>find_simple_exit</code> on RTL. Finally, there are functions that
  105. provide the same information, but additionally cache it, so that
  106. repeated calls to number of iterations are not so costly &ndash;
  107. <code>number_of_latch_executions</code> on GIMPLE and <code>get_simple_loop_desc</code>
  108. on RTL.
  109. </p>
  110. <p>Note that some of these functions may behave slightly differently than
  111. others &ndash; some of them return only the expression for the number of
  112. iterations, and fail if there are some assumptions. The function
  113. <code>number_of_latch_executions</code> works only for single-exit loops.
  114. The function <code>number_of_cond_exit_executions</code> can be used to
  115. determine number of executions of the exit condition of a single-exit
  116. loop (i.e., the <code>number_of_latch_executions</code> increased by one).
  117. </p>
  118. <p>On GIMPLE, below constraint flags affect semantics of some APIs of number
  119. of iterations analyzer:
  120. </p>
  121. <ul>
  122. <li> <code>LOOP_C_INFINITE</code>: If this constraint flag is set, the loop
  123. is known to be infinite. APIs like <code>number_of_iterations_exit</code> can
  124. return false directly without doing any analysis.
  125. </li><li> <code>LOOP_C_FINITE</code>: If this constraint flag is set, the loop is
  126. known to be finite, in other words, loop&rsquo;s number of iterations can be
  127. computed with <code>assumptions</code> be true.
  128. </li></ul>
  129. <p>Generally, the constraint flags are set/cleared by consumers which are
  130. loop optimizers. It&rsquo;s also the consumers&rsquo; responsibility to set/clear
  131. constraints correctly. Failing to do that might result in hard to track
  132. down bugs in scev/niter consumers. One typical use case is vectorizer:
  133. it drives number of iterations analyzer by setting <code>LOOP_C_FINITE</code>
  134. and vectorizes possibly infinite loop by versioning loop with analysis
  135. result. In return, constraints set by consumers can also help number of
  136. iterations analyzer in following optimizers. For example, <code>niter</code>
  137. of a loop versioned under <code>assumptions</code> is valid unconditionally.
  138. </p>
  139. <p>Other constraints may be added in the future, for example, a constraint
  140. indicating that loops&rsquo; latch must roll thus <code>may_be_zero</code> would be
  141. false unconditionally.
  142. </p>
  143. <hr>
  144. <div class="header">
  145. <p>
  146. Next: <a href="Dependency-analysis.html#Dependency-analysis" accesskey="n" rel="next">Dependency analysis</a>, Previous: <a href="loop_002div.html#loop_002div" accesskey="p" rel="prev">loop-iv</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>
  147. </div>
  148. </body>
  149. </html>