| <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> |
| <html> |
| <!-- Copyright (C) 1988-2015 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.2, http://www.gnu.org/software/texinfo/ --> |
| <head> |
| <title>GNU Compiler Collection (GCC) Internals: Loop representation</title> |
| |
| <meta name="description" content="GNU Compiler Collection (GCC) Internals: Loop representation"> |
| <meta name="keywords" content="GNU Compiler Collection (GCC) Internals: Loop representation"> |
| <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-querying.html#Loop-querying" rel="next" title="Loop querying"> |
| <link href="Loop-Analysis-and-Representation.html#Loop-Analysis-and-Representation" rel="prev" title="Loop Analysis and Representation"> |
| <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="Loop-representation"></a> |
| <div class="header"> |
| <p> |
| Next: <a href="Loop-querying.html#Loop-querying" accesskey="n" rel="next">Loop querying</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="Loop-representation-1"></a> |
| <h3 class="section">15.1 Loop representation</h3> |
| <a name="index-Loop-representation"></a> |
| <a name="index-Loop-analysis"></a> |
| |
| <p>This chapter describes the representation of loops in GCC, and functions |
| that can be used to build, modify and analyze this representation. Most |
| of the interfaces and data structures are declared in <samp>cfgloop.h</samp>. |
| Loop structures are analyzed and this information disposed or updated |
| at the discretion of individual passes. Still most of the generic |
| CFG manipulation routines are aware of loop structures and try to |
| keep them up-to-date. By this means an increasing part of the |
| compilation pipeline is setup to maintain loop structure across |
| passes to allow attaching meta information to individual loops |
| for consumption by later passes. |
| </p> |
| <p>In general, a natural loop has one entry block (header) and possibly |
| several back edges (latches) leading to the header from the inside of |
| the loop. Loops with several latches may appear if several loops share |
| a single header, or if there is a branching in the middle of the loop. |
| The representation of loops in GCC however allows only loops with a |
| single latch. During loop analysis, headers of such loops are split and |
| forwarder blocks are created in order to disambiguate their structures. |
| Heuristic based on profile information and structure of the induction |
| variables in the loops is used to determine whether the latches |
| correspond to sub-loops or to control flow in a single loop. This means |
| that the analysis sometimes changes the CFG, and if you run it in the |
| middle of an optimization pass, you must be able to deal with the new |
| blocks. You may avoid CFG changes by passing |
| <code>LOOPS_MAY_HAVE_MULTIPLE_LATCHES</code> flag to the loop discovery, |
| note however that most other loop manipulation functions will not work |
| correctly for loops with multiple latch edges (the functions that only |
| query membership of blocks to loops and subloop relationships, or |
| enumerate and test loop exits, can be expected to work). |
| </p> |
| <p>Body of the loop is the set of blocks that are dominated by its header, |
| and reachable from its latch against the direction of edges in CFG. The |
| loops are organized in a containment hierarchy (tree) such that all the |
| loops immediately contained inside loop L are the children of L in the |
| tree. This tree is represented by the <code>struct loops</code> structure. |
| The root of this tree is a fake loop that contains all blocks in the |
| function. Each of the loops is represented in a <code>struct loop</code> |
| structure. Each loop is assigned an index (<code>num</code> field of the |
| <code>struct loop</code> structure), and the pointer to the loop is stored in |
| the corresponding field of the <code>larray</code> vector in the loops |
| structure. The indices do not have to be continuous, there may be |
| empty (<code>NULL</code>) entries in the <code>larray</code> created by deleting |
| loops. Also, there is no guarantee on the relative order of a loop |
| and its subloops in the numbering. The index of a loop never changes. |
| </p> |
| <p>The entries of the <code>larray</code> field should not be accessed directly. |
| The function <code>get_loop</code> returns the loop description for a loop with |
| the given index. <code>number_of_loops</code> function returns number of |
| loops in the function. To traverse all loops, use <code>FOR_EACH_LOOP</code> |
| macro. The <code>flags</code> argument of the macro is used to determine |
| the direction of traversal and the set of loops visited. Each loop is |
| guaranteed to be visited exactly once, regardless of the changes to the |
| loop tree, and the loops may be removed during the traversal. The newly |
| created loops are never traversed, if they need to be visited, this |
| must be done separately after their creation. The <code>FOR_EACH_LOOP</code> |
| macro allocates temporary variables. If the <code>FOR_EACH_LOOP</code> loop |
| were ended using break or goto, they would not be released; |
| <code>FOR_EACH_LOOP_BREAK</code> macro must be used instead. |
| </p> |
| <p>Each basic block contains the reference to the innermost loop it belongs |
| to (<code>loop_father</code>). For this reason, it is only possible to have |
| one <code>struct loops</code> structure initialized at the same time for each |
| CFG. The global variable <code>current_loops</code> contains the |
| <code>struct loops</code> structure. Many of the loop manipulation functions |
| assume that dominance information is up-to-date. |
| </p> |
| <p>The loops are analyzed through <code>loop_optimizer_init</code> function. The |
| argument of this function is a set of flags represented in an integer |
| bitmask. These flags specify what other properties of the loop |
| structures should be calculated/enforced and preserved later: |
| </p> |
| <ul> |
| <li> <code>LOOPS_MAY_HAVE_MULTIPLE_LATCHES</code>: If this flag is set, no |
| changes to CFG will be performed in the loop analysis, in particular, |
| loops with multiple latch edges will not be disambiguated. If a loop |
| has multiple latches, its latch block is set to NULL. Most of |
| the loop manipulation functions will not work for loops in this shape. |
| No other flags that require CFG changes can be passed to |
| loop_optimizer_init. |
| </li><li> <code>LOOPS_HAVE_PREHEADERS</code>: Forwarder blocks are created in such |
| a way that each loop has only one entry edge, and additionally, the |
| source block of this entry edge has only one successor. This creates a |
| natural place where the code can be moved out of the loop, and ensures |
| that the entry edge of the loop leads from its immediate super-loop. |
| </li><li> <code>LOOPS_HAVE_SIMPLE_LATCHES</code>: Forwarder blocks are created to |
| force the latch block of each loop to have only one successor. This |
| ensures that the latch of the loop does not belong to any of its |
| sub-loops, and makes manipulation with the loops significantly easier. |
| Most of the loop manipulation functions assume that the loops are in |
| this shape. Note that with this flag, the “normal” loop without any |
| control flow inside and with one exit consists of two basic blocks. |
| </li><li> <code>LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS</code>: Basic blocks and |
| edges in the strongly connected components that are not natural loops |
| (have more than one entry block) are marked with |
| <code>BB_IRREDUCIBLE_LOOP</code> and <code>EDGE_IRREDUCIBLE_LOOP</code> flags. The |
| flag is not set for blocks and edges that belong to natural loops that |
| are in such an irreducible region (but it is set for the entry and exit |
| edges of such a loop, if they lead to/from this region). |
| </li><li> <code>LOOPS_HAVE_RECORDED_EXITS</code>: The lists of exits are recorded |
| and updated for each loop. This makes some functions (e.g., |
| <code>get_loop_exit_edges</code>) more efficient. Some functions (e.g., |
| <code>single_exit</code>) can be used only if the lists of exits are |
| recorded. |
| </li></ul> |
| |
| <p>These properties may also be computed/enforced later, using functions |
| <code>create_preheaders</code>, <code>force_single_succ_latches</code>, |
| <code>mark_irreducible_loops</code> and <code>record_loop_exits</code>. |
| The properties can be queried using <code>loops_state_satisfies_p</code>. |
| </p> |
| <p>The memory occupied by the loops structures should be freed with |
| <code>loop_optimizer_finalize</code> function. When loop structures are |
| setup to be preserved across passes this function reduces the |
| information to be kept up-to-date to a minimum (only |
| <code>LOOPS_MAY_HAVE_MULTIPLE_LATCHES</code> set). |
| </p> |
| <p>The CFG manipulation functions in general do not update loop structures. |
| Specialized versions that additionally do so are provided for the most |
| common tasks. On GIMPLE, <code>cleanup_tree_cfg_loop</code> function can be |
| used to cleanup CFG while updating the loops structures if |
| <code>current_loops</code> is set. |
| </p> |
| <p>At the moment loop structure is preserved from the start of GIMPLE |
| loop optimizations until the end of RTL loop optimizations. During |
| this time a loop can be tracked by its <code>struct loop</code> and number. |
| </p> |
| <hr> |
| <div class="header"> |
| <p> |
| Next: <a href="Loop-querying.html#Loop-querying" accesskey="n" rel="next">Loop querying</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> |
