1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
<!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: RTL SSA Basic Blocks</title>
<meta name="description" content="GNU Compiler Collection (GCC) Internals: RTL SSA Basic Blocks">
<meta name="keywords" content="GNU Compiler Collection (GCC) Internals: RTL SSA Basic Blocks">
<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="RTL-SSA.html#RTL-SSA" rel="up" title="RTL SSA">
<link href="RTL-SSA-Resources.html#RTL-SSA-Resources" rel="next" title="RTL SSA Resources">
<link href="RTL-SSA-Instructions.html#RTL-SSA-Instructions" rel="previous" title="RTL SSA Instructions">
<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-SSA-Basic-Blocks"></a>
<div class="header">
<p>
Next: <a href="RTL-SSA-Resources.html#RTL-SSA-Resources" accesskey="n" rel="next">RTL SSA Resources</a>, Previous: <a href="RTL-SSA-Instructions.html#RTL-SSA-Instructions" accesskey="p" rel="previous">RTL SSA Instructions</a>, Up: <a href="RTL-SSA.html#RTL-SSA" accesskey="u" rel="up">RTL SSA</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-SSA-Basic-Blocks-1"></a>
<h4 class="subsection">14.21.3 RTL SSA Basic Blocks</h4>
<a name="index-basic-blocks_002c-RTL-SSA"></a>
<a name="index-basic_005fblock"></a>
<a name="index-rtl_005fssa_003a_003abb_005finfo"></a>
<p>RTL SSA instructions (see <a href="RTL-SSA-Instructions.html#RTL-SSA-Instructions">RTL SSA Instructions</a>) are organized into
basic blocks, with each block being represented by an <code>rtl_ssa:bb_info</code>.
There is a one-to-one mapping between these <code>rtl_ssa:bb_info</code>
structures and the underlying CFG <code>basic_block</code> structures
(see <a href="Basic-Blocks.html#Basic-Blocks">Basic Blocks</a>).
</p>
<a name="index-_0060_0060real_0027_0027-instructions_002c-RTL-SSA"></a>
<a name="real-RTL-SSA-insns"></a><p>If a CFG basic block <var>bb</var> contains an RTL instruction <var>insn</var>,
the RTL SSA represenation of <var>bb</var> also contains an RTL SSA representation
of <var>insn</var><a name="DOCF5" href="#FOOT5"><sup>5</sup></a>. Within RTL SSA, these instructions are referred to as
“real” instructions. These real instructions fall into two groups:
debug instructions and nondebug instructions. Only nondebug instructions
should affect code generation decisions.
</p>
<p>In addition, each RTL SSA basic block has two “artificial”
instructions: a “head” instruction that comes before all the real
instructions and an “end” instruction that comes after all real
instructions. These instructions exist to represent things that
are conceptually defined or used at the start and end of a basic block.
The instructions always exist, even if they do not currently do anything.
</p>
<p>Like instructions, these blocks are chained together in a reverse
postorder. This list includes the entry block (which always comes
first) and the exit block (which always comes last).
</p>
<a name="index-extended-basic-blocks_002c-RTL-SSA"></a>
<a name="index-rtl_005fssa_003a_003aebb_005finfo"></a>
<p>RTL SSA basic blocks are chained together into “extended basic blocks”
(EBBs), represented by an <code>rtl_ssa::ebb_info</code>. Extended basic
blocks contain one or more basic blocks. They have the property
that if a block <var>bby</var> comes immediately after a block <var>bbx</var>
in an EBB, then <var>bby</var> can only be reached by <var>bbx</var>; in other words,
<var>bbx</var> is the sole predecessor of <var>bby</var>.
</p>
<p>Each extended basic block starts with an artificial “phi node”
instruction. This instruction defines all phi nodes for the EBB
(see <a href="RTL-SSA-Phi-Nodes.html#RTL-SSA-Phi-Nodes">RTL SSA Phi Nodes</a>). (Individual blocks in an EBB do not
need phi nodes because their live values can only come from one source.)
</p>
<p>The contents of a function are therefore represented using a
four-level hierarchy:
</p>
<ul>
<li> functions (<code>rtl_ssa::function_info</code>), which contain …
</li><li> extended basic blocks (<code>rtl_ssa::ebb_info</code>), which contain …
</li><li> basic blocks (<code>rtl_ssa::bb_info</code>), which contain …
</li><li> instructions (<code>rtl_ssa::insn_info</code>)
</li></ul>
<p>In dumps, a basic block is identified as <code>bb<var>n</var></code>, where <var>n</var>
is the index of the associated CFG <code>basic_block</code> structure.
An EBB is in turn identified by the index of its first block.
For example, an EBB that contains ‘<samp>bb10</samp>’, <code>bb5</code>, <code>bb6</code>
and <code>bb9</code> is identified as <var>ebb10</var>.
</p>
<div class="footnote">
<hr>
<h4 class="footnotes-heading">Footnotes</h4>
<h3><a name="FOOT5" href="#DOCF5">(5)</a></h3>
<p>Note that this excludes non-instruction things like
<code>note</code>s and <code>barrier</code>s that also appear in the chain of RTL
instructions.</p>
</div>
<hr>
<div class="header">
<p>
Next: <a href="RTL-SSA-Resources.html#RTL-SSA-Resources" accesskey="n" rel="next">RTL SSA Resources</a>, Previous: <a href="RTL-SSA-Instructions.html#RTL-SSA-Instructions" accesskey="p" rel="previous">RTL SSA Instructions</a>, Up: <a href="RTL-SSA.html#RTL-SSA" accesskey="u" rel="up">RTL SSA</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>
|
