diff options
| author | alk3pInjection <webmaster@raspii.tech> | 2024-02-04 16:16:35 +0800 |
|---|---|---|
| committer | alk3pInjection <webmaster@raspii.tech> | 2024-02-04 16:16:35 +0800 |
| commit | abdaadbcae30fe0c9a66c7516798279fdfd97750 (patch) | |
| tree | 00a54a6e25601e43876d03c1a4a12a749d4a914c /share/doc/gccint/Scalar-evolutions.html | |
https://developer.arm.com/downloads/-/arm-gnu-toolchain-downloads
Change-Id: I7303388733328cd98ab9aa3c30236db67f2e9e9c
Diffstat (limited to 'share/doc/gccint/Scalar-evolutions.html')
| -rw-r--r-- | share/doc/gccint/Scalar-evolutions.html | 151 |
1 files changed, 151 insertions, 0 deletions
diff --git a/share/doc/gccint/Scalar-evolutions.html b/share/doc/gccint/Scalar-evolutions.html new file mode 100644 index 0000000..da34f40 --- /dev/null +++ b/share/doc/gccint/Scalar-evolutions.html @@ -0,0 +1,151 @@ +<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> +<html> +<!-- Copyright (C) 1988-2023 Free Software Foundation, Inc. + +Permission is granted to copy, distribute and/or modify this document +under the terms of the GNU Free Documentation License, Version 1.3 or +any later version published by the Free Software Foundation; with the +Invariant Sections being "Funding Free Software", the Front-Cover +Texts being (a) (see below), and with the Back-Cover Texts being (b) +(see below). A copy of the license is included in the section entitled +"GNU Free Documentation License". + +(a) The FSF's Front-Cover Text is: + +A GNU Manual + +(b) The FSF's Back-Cover Text is: + +You have freedom to copy and modify this GNU Manual, like GNU + software. Copies published by the Free Software Foundation raise + funds for GNU development. --> +<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ --> +<head> +<title>GNU Compiler Collection (GCC) Internals: Scalar evolutions</title> + +<meta name="description" content="GNU Compiler Collection (GCC) Internals: Scalar evolutions"> +<meta name="keywords" content="GNU Compiler Collection (GCC) Internals: Scalar evolutions"> +<meta name="resource-type" content="document"> +<meta name="distribution" content="global"> +<meta name="Generator" content="makeinfo"> +<meta http-equiv="Content-Type" content="text/html; charset=utf-8"> +<link href="index.html#Top" rel="start" title="Top"> +<link href="Option-Index.html#Option-Index" rel="index" title="Option Index"> +<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents"> +<link href="Loop-Analysis-and-Representation.html#Loop-Analysis-and-Representation" rel="up" title="Loop Analysis and Representation"> +<link href="loop_002div.html#loop_002div" rel="next" title="loop-iv"> +<link href="LCSSA.html#LCSSA" rel="previous" title="LCSSA"> +<style type="text/css"> +<!-- +a.summary-letter {text-decoration: none} +blockquote.smallquotation {font-size: smaller} +div.display {margin-left: 3.2em} +div.example {margin-left: 3.2em} +div.indentedblock {margin-left: 3.2em} +div.lisp {margin-left: 3.2em} +div.smalldisplay {margin-left: 3.2em} +div.smallexample {margin-left: 3.2em} +div.smallindentedblock {margin-left: 3.2em; font-size: smaller} +div.smalllisp {margin-left: 3.2em} +kbd {font-style:oblique} +pre.display {font-family: inherit} +pre.format {font-family: inherit} +pre.menu-comment {font-family: serif} +pre.menu-preformatted {font-family: serif} +pre.smalldisplay {font-family: inherit; font-size: smaller} +pre.smallexample {font-size: smaller} +pre.smallformat {font-family: inherit; font-size: smaller} +pre.smalllisp {font-size: smaller} +span.nocodebreak {white-space:nowrap} +span.nolinebreak {white-space:nowrap} +span.roman {font-family:serif; font-weight:normal} +span.sansserif {font-family:sans-serif; font-weight:normal} +ul.no-bullet {list-style: none} +--> +</style> + + +</head> + +<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000"> +<a name="Scalar-evolutions"></a> +<div class="header"> +<p> +Next: <a href="loop_002div.html#loop_002div" accesskey="n" rel="next">loop-iv</a>, Previous: <a href="LCSSA.html#LCSSA" accesskey="p" rel="previous">LCSSA</a>, Up: <a href="Loop-Analysis-and-Representation.html#Loop-Analysis-and-Representation" accesskey="u" rel="up">Loop Analysis and Representation</a> [<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> +</div> +<hr> +<a name="Scalar-evolutions-1"></a> +<h3 class="section">16.5 Scalar evolutions</h3> +<a name="index-Scalar-evolutions"></a> +<a name="index-IV-analysis-on-GIMPLE"></a> + +<p>Scalar evolutions (SCEV) are used to represent results of induction +variable analysis on GIMPLE. They enable us to represent variables with +complicated behavior in a simple and consistent way (we only use it to +express values of polynomial induction variables, but it is possible to +extend it). The interfaces to SCEV analysis are declared in +<samp>tree-scalar-evolution.h</samp>. To use scalar evolutions analysis, +<code>scev_initialize</code> must be used. To stop using SCEV, +<code>scev_finalize</code> should be used. SCEV analysis caches results in +order to save time and memory. This cache however is made invalid by +most of the loop transformations, including removal of code. If such a +transformation is performed, <code>scev_reset</code> must be called to clean +the caches. +</p> +<p>Given an SSA name, its behavior in loops can be analyzed using the +<code>analyze_scalar_evolution</code> function. The returned SCEV however +does not have to be fully analyzed and it may contain references to +other SSA names defined in the loop. To resolve these (potentially +recursive) references, <code>instantiate_parameters</code> or +<code>resolve_mixers</code> functions must be used. +<code>instantiate_parameters</code> is useful when you use the results of SCEV +only for some analysis, and when you work with whole nest of loops at +once. It will try replacing all SSA names by their SCEV in all loops, +including the super-loops of the current loop, thus providing a complete +information about the behavior of the variable in the loop nest. +<code>resolve_mixers</code> is useful if you work with only one loop at a +time, and if you possibly need to create code based on the value of the +induction variable. It will only resolve the SSA names defined in the +current loop, leaving the SSA names defined outside unchanged, even if +their evolution in the outer loops is known. +</p> +<p>The SCEV is a normal tree expression, except for the fact that it may +contain several special tree nodes. One of them is +<code>SCEV_NOT_KNOWN</code>, used for SSA names whose value cannot be +expressed. The other one is <code>POLYNOMIAL_CHREC</code>. Polynomial chrec +has three arguments – base, step and loop (both base and step may +contain further polynomial chrecs). Type of the expression and of base +and step must be the same. A variable has evolution +<code>POLYNOMIAL_CHREC(base, step, loop)</code> if it is (in the specified +loop) equivalent to <code>x_1</code> in the following example +</p> +<div class="smallexample"> +<pre class="smallexample">while (…) + { + x_1 = phi (base, x_2); + x_2 = x_1 + step; + } +</pre></div> + +<p>Note that this includes the language restrictions on the operations. +For example, if we compile C code and <code>x</code> has signed type, then the +overflow in addition would cause undefined behavior, and we may assume +that this does not happen. Hence, the value with this SCEV cannot +overflow (which restricts the number of iterations of such a loop). +</p> +<p>In many cases, one wants to restrict the attention just to affine +induction variables. In this case, the extra expressive power of SCEV +is not useful, and may complicate the optimizations. In this case, +<code>simple_iv</code> function may be used to analyze a value – the result +is a loop-invariant base and step. +</p> +<hr> +<div class="header"> +<p> +Next: <a href="loop_002div.html#loop_002div" accesskey="n" rel="next">loop-iv</a>, Previous: <a href="LCSSA.html#LCSSA" accesskey="p" rel="previous">LCSSA</a>, Up: <a href="Loop-Analysis-and-Representation.html#Loop-Analysis-and-Representation" accesskey="u" rel="up">Loop Analysis and Representation</a> [<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> +</div> + + + +</body> +</html> |