358 lines
16 KiB
HTML
358 lines
16 KiB
HTML
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
|
|
<html>
|
|
<!-- Copyright (C) 1988-2016 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: RTL passes</title>
|
|
|
|
<meta name="description" content="GNU Compiler Collection (GCC) Internals: RTL passes">
|
|
<meta name="keywords" content="GNU Compiler Collection (GCC) Internals: RTL passes">
|
|
<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="Passes.html#Passes" rel="up" title="Passes">
|
|
<link href="Optimization-info.html#Optimization-info" rel="next" title="Optimization info">
|
|
<link href="Tree-SSA-passes.html#Tree-SSA-passes" rel="prev" title="Tree SSA passes">
|
|
<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="RTL-passes"></a>
|
|
<div class="header">
|
|
<p>
|
|
Next: <a href="Optimization-info.html#Optimization-info" accesskey="n" rel="next">Optimization info</a>, Previous: <a href="Tree-SSA-passes.html#Tree-SSA-passes" accesskey="p" rel="prev">Tree SSA passes</a>, Up: <a href="Passes.html#Passes" accesskey="u" rel="up">Passes</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="RTL-passes-1"></a>
|
|
<h3 class="section">9.6 RTL passes</h3>
|
|
|
|
<p>The following briefly describes the RTL generation and optimization
|
|
passes that are run after the Tree optimization passes.
|
|
</p>
|
|
<ul>
|
|
<li> RTL generation
|
|
|
|
<p>The source files for RTL generation include
|
|
<samp>stmt.c</samp>,
|
|
<samp>calls.c</samp>,
|
|
<samp>expr.c</samp>,
|
|
<samp>explow.c</samp>,
|
|
<samp>expmed.c</samp>,
|
|
<samp>function.c</samp>,
|
|
<samp>optabs.c</samp>
|
|
and <samp>emit-rtl.c</samp>.
|
|
Also, the file
|
|
<samp>insn-emit.c</samp>, generated from the machine description by the
|
|
program <code>genemit</code>, is used in this pass. The header file
|
|
<samp>expr.h</samp> is used for communication within this pass.
|
|
</p>
|
|
<a name="index-genflags"></a>
|
|
<a name="index-gencodes"></a>
|
|
<p>The header files <samp>insn-flags.h</samp> and <samp>insn-codes.h</samp>,
|
|
generated from the machine description by the programs <code>genflags</code>
|
|
and <code>gencodes</code>, tell this pass which standard names are available
|
|
for use and which patterns correspond to them.
|
|
</p>
|
|
</li><li> Generation of exception landing pads
|
|
|
|
<p>This pass generates the glue that handles communication between the
|
|
exception handling library routines and the exception handlers within
|
|
the function. Entry points in the function that are invoked by the
|
|
exception handling library are called <em>landing pads</em>. The code
|
|
for this pass is located in <samp>except.c</samp>.
|
|
</p>
|
|
</li><li> Control flow graph cleanup
|
|
|
|
<p>This pass removes unreachable code, simplifies jumps to next, jumps to
|
|
jump, jumps across jumps, etc. The pass is run multiple times.
|
|
For historical reasons, it is occasionally referred to as the “jump
|
|
optimization pass”. The bulk of the code for this pass is in
|
|
<samp>cfgcleanup.c</samp>, and there are support routines in <samp>cfgrtl.c</samp>
|
|
and <samp>jump.c</samp>.
|
|
</p>
|
|
</li><li> Forward propagation of single-def values
|
|
|
|
<p>This pass attempts to remove redundant computation by substituting
|
|
variables that come from a single definition, and
|
|
seeing if the result can be simplified. It performs copy propagation
|
|
and addressing mode selection. The pass is run twice, with values
|
|
being propagated into loops only on the second run. The code is
|
|
located in <samp>fwprop.c</samp>.
|
|
</p>
|
|
</li><li> Common subexpression elimination
|
|
|
|
<p>This pass removes redundant computation within basic blocks, and
|
|
optimizes addressing modes based on cost. The pass is run twice.
|
|
The code for this pass is located in <samp>cse.c</samp>.
|
|
</p>
|
|
</li><li> Global common subexpression elimination
|
|
|
|
<p>This pass performs two
|
|
different types of GCSE depending on whether you are optimizing for
|
|
size or not (LCM based GCSE tends to increase code size for a gain in
|
|
speed, while Morel-Renvoise based GCSE does not).
|
|
When optimizing for size, GCSE is done using Morel-Renvoise Partial
|
|
Redundancy Elimination, with the exception that it does not try to move
|
|
invariants out of loops—that is left to the loop optimization pass.
|
|
If MR PRE GCSE is done, code hoisting (aka unification) is also done, as
|
|
well as load motion.
|
|
If you are optimizing for speed, LCM (lazy code motion) based GCSE is
|
|
done. LCM is based on the work of Knoop, Ruthing, and Steffen. LCM
|
|
based GCSE also does loop invariant code motion. We also perform load
|
|
and store motion when optimizing for speed.
|
|
Regardless of which type of GCSE is used, the GCSE pass also performs
|
|
global constant and copy propagation.
|
|
The source file for this pass is <samp>gcse.c</samp>, and the LCM routines
|
|
are in <samp>lcm.c</samp>.
|
|
</p>
|
|
</li><li> Loop optimization
|
|
|
|
<p>This pass performs several loop related optimizations.
|
|
The source files <samp>cfgloopanal.c</samp> and <samp>cfgloopmanip.c</samp> contain
|
|
generic loop analysis and manipulation code. Initialization and finalization
|
|
of loop structures is handled by <samp>loop-init.c</samp>.
|
|
A loop invariant motion pass is implemented in <samp>loop-invariant.c</samp>.
|
|
Basic block level optimizations—unrolling, and peeling loops—
|
|
are implemented in <samp>loop-unroll.c</samp>.
|
|
Replacing of the exit condition of loops by special machine-dependent
|
|
instructions is handled by <samp>loop-doloop.c</samp>.
|
|
</p>
|
|
</li><li> Jump bypassing
|
|
|
|
<p>This pass is an aggressive form of GCSE that transforms the control
|
|
flow graph of a function by propagating constants into conditional
|
|
branch instructions. The source file for this pass is <samp>gcse.c</samp>.
|
|
</p>
|
|
</li><li> If conversion
|
|
|
|
<p>This pass attempts to replace conditional branches and surrounding
|
|
assignments with arithmetic, boolean value producing comparison
|
|
instructions, and conditional move instructions. In the very last
|
|
invocation after reload/LRA, it will generate predicated instructions
|
|
when supported by the target. The code is located in <samp>ifcvt.c</samp>.
|
|
</p>
|
|
</li><li> Web construction
|
|
|
|
<p>This pass splits independent uses of each pseudo-register. This can
|
|
improve effect of the other transformation, such as CSE or register
|
|
allocation. The code for this pass is located in <samp>web.c</samp>.
|
|
</p>
|
|
</li><li> Instruction combination
|
|
|
|
<p>This pass attempts to combine groups of two or three instructions that
|
|
are related by data flow into single instructions. It combines the
|
|
RTL expressions for the instructions by substitution, simplifies the
|
|
result using algebra, and then attempts to match the result against
|
|
the machine description. The code is located in <samp>combine.c</samp>.
|
|
</p>
|
|
</li><li> Mode switching optimization
|
|
|
|
<p>This pass looks for instructions that require the processor to be in a
|
|
specific “mode” and minimizes the number of mode changes required to
|
|
satisfy all users. What these modes are, and what they apply to are
|
|
completely target-specific. The code for this pass is located in
|
|
<samp>mode-switching.c</samp>.
|
|
</p>
|
|
</li><li> <a name="index-modulo-scheduling"></a>
|
|
<a name="index-sms_002c-swing_002c-software-pipelining"></a>
|
|
Modulo scheduling
|
|
|
|
<p>This pass looks at innermost loops and reorders their instructions
|
|
by overlapping different iterations. Modulo scheduling is performed
|
|
immediately before instruction scheduling. The code for this pass is
|
|
located in <samp>modulo-sched.c</samp>.
|
|
</p>
|
|
</li><li> Instruction scheduling
|
|
|
|
<p>This pass looks for instructions whose output will not be available by
|
|
the time that it is used in subsequent instructions. Memory loads and
|
|
floating point instructions often have this behavior on RISC machines.
|
|
It re-orders instructions within a basic block to try to separate the
|
|
definition and use of items that otherwise would cause pipeline
|
|
stalls. This pass is performed twice, before and after register
|
|
allocation. The code for this pass is located in <samp>haifa-sched.c</samp>,
|
|
<samp>sched-deps.c</samp>, <samp>sched-ebb.c</samp>, <samp>sched-rgn.c</samp> and
|
|
<samp>sched-vis.c</samp>.
|
|
</p>
|
|
</li><li> Register allocation
|
|
|
|
<p>These passes make sure that all occurrences of pseudo registers are
|
|
eliminated, either by allocating them to a hard register, replacing
|
|
them by an equivalent expression (e.g. a constant) or by placing
|
|
them on the stack. This is done in several subpasses:
|
|
</p>
|
|
<ul>
|
|
<li> The integrated register allocator (<acronym>IRA</acronym>). It is called
|
|
integrated because coalescing, register live range splitting, and hard
|
|
register preferencing are done on-the-fly during coloring. It also
|
|
has better integration with the reload/LRA pass. Pseudo-registers spilled
|
|
by the allocator or the reload/LRA have still a chance to get
|
|
hard-registers if the reload/LRA evicts some pseudo-registers from
|
|
hard-registers. The allocator helps to choose better pseudos for
|
|
spilling based on their live ranges and to coalesce stack slots
|
|
allocated for the spilled pseudo-registers. IRA is a regional
|
|
register allocator which is transformed into Chaitin-Briggs allocator
|
|
if there is one region. By default, IRA chooses regions using
|
|
register pressure but the user can force it to use one region or
|
|
regions corresponding to all loops.
|
|
|
|
<p>Source files of the allocator are <samp>ira.c</samp>, <samp>ira-build.c</samp>,
|
|
<samp>ira-costs.c</samp>, <samp>ira-conflicts.c</samp>, <samp>ira-color.c</samp>,
|
|
<samp>ira-emit.c</samp>, <samp>ira-lives</samp>, plus header files <samp>ira.h</samp>
|
|
and <samp>ira-int.h</samp> used for the communication between the allocator
|
|
and the rest of the compiler and between the IRA files.
|
|
</p>
|
|
</li><li> <a name="index-reloading"></a>
|
|
Reloading. This pass renumbers pseudo registers with the hardware
|
|
registers numbers they were allocated. Pseudo registers that did not
|
|
get hard registers are replaced with stack slots. Then it finds
|
|
instructions that are invalid because a value has failed to end up in
|
|
a register, or has ended up in a register of the wrong kind. It fixes
|
|
up these instructions by reloading the problematical values
|
|
temporarily into registers. Additional instructions are generated to
|
|
do the copying.
|
|
|
|
<p>The reload pass also optionally eliminates the frame pointer and inserts
|
|
instructions to save and restore call-clobbered registers around calls.
|
|
</p>
|
|
<p>Source files are <samp>reload.c</samp> and <samp>reload1.c</samp>, plus the header
|
|
<samp>reload.h</samp> used for communication between them.
|
|
</p>
|
|
</li><li> <a name="index-Local-Register-Allocator-_0028LRA_0029"></a>
|
|
This pass is a modern replacement of the reload pass. Source files
|
|
are <samp>lra.c</samp>, <samp>lra-assign.c</samp>, <samp>lra-coalesce.c</samp>,
|
|
<samp>lra-constraints.c</samp>, <samp>lra-eliminations.c</samp>,
|
|
<samp>lra-lives.c</samp>, <samp>lra-remat.c</samp>, <samp>lra-spills.c</samp>, the
|
|
header <samp>lra-int.h</samp> used for communication between them, and the
|
|
header <samp>lra.h</samp> used for communication between LRA and the rest of
|
|
compiler.
|
|
|
|
<p>Unlike the reload pass, intermediate LRA decisions are reflected in
|
|
RTL as much as possible. This reduces the number of target-dependent
|
|
macros and hooks, leaving instruction constraints as the primary
|
|
source of control.
|
|
</p>
|
|
<p>LRA is run on targets for which TARGET_LRA_P returns true.
|
|
</p></li></ul>
|
|
|
|
</li><li> Basic block reordering
|
|
|
|
<p>This pass implements profile guided code positioning. If profile
|
|
information is not available, various types of static analysis are
|
|
performed to make the predictions normally coming from the profile
|
|
feedback (IE execution frequency, branch probability, etc). It is
|
|
implemented in the file <samp>bb-reorder.c</samp>, and the various
|
|
prediction routines are in <samp>predict.c</samp>.
|
|
</p>
|
|
</li><li> Variable tracking
|
|
|
|
<p>This pass computes where the variables are stored at each
|
|
position in code and generates notes describing the variable locations
|
|
to RTL code. The location lists are then generated according to these
|
|
notes to debug information if the debugging information format supports
|
|
location lists. The code is located in <samp>var-tracking.c</samp>.
|
|
</p>
|
|
</li><li> Delayed branch scheduling
|
|
|
|
<p>This optional pass attempts to find instructions that can go into the
|
|
delay slots of other instructions, usually jumps and calls. The code
|
|
for this pass is located in <samp>reorg.c</samp>.
|
|
</p>
|
|
</li><li> Branch shortening
|
|
|
|
<p>On many RISC machines, branch instructions have a limited range.
|
|
Thus, longer sequences of instructions must be used for long branches.
|
|
In this pass, the compiler figures out what how far each instruction
|
|
will be from each other instruction, and therefore whether the usual
|
|
instructions, or the longer sequences, must be used for each branch.
|
|
The code for this pass is located in <samp>final.c</samp>.
|
|
</p>
|
|
</li><li> Register-to-stack conversion
|
|
|
|
<p>Conversion from usage of some hard registers to usage of a register
|
|
stack may be done at this point. Currently, this is supported only
|
|
for the floating-point registers of the Intel 80387 coprocessor. The
|
|
code for this pass is located in <samp>reg-stack.c</samp>.
|
|
</p>
|
|
</li><li> Final
|
|
|
|
<p>This pass outputs the assembler code for the function. The source files
|
|
are <samp>final.c</samp> plus <samp>insn-output.c</samp>; the latter is generated
|
|
automatically from the machine description by the tool <samp>genoutput</samp>.
|
|
The header file <samp>conditions.h</samp> is used for communication between
|
|
these files.
|
|
</p>
|
|
</li><li> Debugging information output
|
|
|
|
<p>This is run after final because it must output the stack slot offsets
|
|
for pseudo registers that did not get hard registers. Source files
|
|
are <samp>dbxout.c</samp> for DBX symbol table format, <samp>sdbout.c</samp> for
|
|
SDB symbol table format, <samp>dwarfout.c</samp> for DWARF symbol table
|
|
format, files <samp>dwarf2out.c</samp> and <samp>dwarf2asm.c</samp> for DWARF2
|
|
symbol table format, and <samp>vmsdbgout.c</samp> for VMS debug symbol table
|
|
format.
|
|
</p>
|
|
</li></ul>
|
|
|
|
<hr>
|
|
<div class="header">
|
|
<p>
|
|
Next: <a href="Optimization-info.html#Optimization-info" accesskey="n" rel="next">Optimization info</a>, Previous: <a href="Tree-SSA-passes.html#Tree-SSA-passes" accesskey="p" rel="prev">Tree SSA passes</a>, Up: <a href="Passes.html#Passes" accesskey="u" rel="up">Passes</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>
|