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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
|
<!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: Looping Patterns</title>
<meta name="description" content="GNU Compiler Collection (GCC) Internals: Looping Patterns">
<meta name="keywords" content="GNU Compiler Collection (GCC) Internals: Looping Patterns">
<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="Machine-Desc.html#Machine-Desc" rel="up" title="Machine Desc">
<link href="Insn-Canonicalizations.html#Insn-Canonicalizations" rel="next" title="Insn Canonicalizations">
<link href="Jump-Patterns.html#Jump-Patterns" rel="previous" title="Jump Patterns">
<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="Looping-Patterns"></a>
<div class="header">
<p>
Next: <a href="Insn-Canonicalizations.html#Insn-Canonicalizations" accesskey="n" rel="next">Insn Canonicalizations</a>, Previous: <a href="Jump-Patterns.html#Jump-Patterns" accesskey="p" rel="previous">Jump Patterns</a>, Up: <a href="Machine-Desc.html#Machine-Desc" accesskey="u" rel="up">Machine Desc</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="Defining-Looping-Instruction-Patterns"></a>
<h3 class="section">17.13 Defining Looping Instruction Patterns</h3>
<a name="index-looping-instruction-patterns"></a>
<a name="index-defining-looping-instruction-patterns"></a>
<p>Some machines have special jump instructions that can be utilized to
make loops more efficient. A common example is the 68000 ‘<samp>dbra</samp>’
instruction which performs a decrement of a register and a branch if the
result was greater than zero. Other machines, in particular digital
signal processors (DSPs), have special block repeat instructions to
provide low-overhead loop support. For example, the TI TMS320C3x/C4x
DSPs have a block repeat instruction that loads special registers to
mark the top and end of a loop and to count the number of loop
iterations. This avoids the need for fetching and executing a
‘<samp>dbra</samp>’-like instruction and avoids pipeline stalls associated with
the jump.
</p>
<p>GCC has two special named patterns to support low overhead looping.
They are ‘<samp>doloop_begin</samp>’ and ‘<samp>doloop_end</samp>’. These are emitted
by the loop optimizer for certain well-behaved loops with a finite
number of loop iterations using information collected during strength
reduction.
</p>
<p>The ‘<samp>doloop_end</samp>’ pattern describes the actual looping instruction
(or the implicit looping operation) and the ‘<samp>doloop_begin</samp>’ pattern
is an optional companion pattern that can be used for initialization
needed for some low-overhead looping instructions.
</p>
<p>Note that some machines require the actual looping instruction to be
emitted at the top of the loop (e.g., the TMS320C3x/C4x DSPs). Emitting
the true RTL for a looping instruction at the top of the loop can cause
problems with flow analysis. So instead, a dummy <code>doloop</code> insn is
emitted at the end of the loop. The machine dependent reorg pass checks
for the presence of this <code>doloop</code> insn and then searches back to
the top of the loop, where it inserts the true looping insn (provided
there are no instructions in the loop which would cause problems). Any
additional labels can be emitted at this point. In addition, if the
desired special iteration counter register was not allocated, this
machine dependent reorg pass could emit a traditional compare and jump
instruction pair.
</p>
<p>For the ‘<samp>doloop_end</samp>’ pattern, the loop optimizer allocates an
additional pseudo register as an iteration counter. This pseudo
register cannot be used within the loop (i.e., general induction
variables cannot be derived from it), however, in many cases the loop
induction variable may become redundant and removed by the flow pass.
</p>
<p>The ‘<samp>doloop_end</samp>’ pattern must have a specific structure to be
handled correctly by GCC. The example below is taken (slightly
simplified) from the PDP-11 target:
</p>
<div class="smallexample">
<pre class="smallexample">(define_expand "doloop_end"
[(parallel [(set (pc)
(if_then_else
(ne (match_operand:HI 0 "nonimmediate_operand" "+r,!m")
(const_int 1))
(label_ref (match_operand 1 "" ""))
(pc)))
(set (match_dup 0)
(plus:HI (match_dup 0)
(const_int -1)))])]
""
"{
if (GET_MODE (operands[0]) != HImode)
FAIL;
}")
(define_insn "doloop_end_insn"
[(set (pc)
(if_then_else
(ne (match_operand:HI 0 "nonimmediate_operand" "+r,!m")
(const_int 1))
(label_ref (match_operand 1 "" ""))
(pc)))
(set (match_dup 0)
(plus:HI (match_dup 0)
(const_int -1)))]
""
{
if (which_alternative == 0)
return "sob %0,%l1";
/* emulate sob */
output_asm_insn ("dec %0", operands);
return "bne %l1";
})
</pre></div>
<p>The first part of the pattern describes the branch condition. GCC
supports three cases for the way the target machine handles the loop
counter:
</p><ul>
<li> Loop terminates when the loop register decrements to zero. This
is represented by a <code>ne</code> comparison of the register (its old value)
with constant 1 (as in the example above).
</li><li> Loop terminates when the loop register decrements to -1.
This is represented by a <code>ne</code> comparison of the register with
constant zero.
</li><li> Loop terminates when the loop register decrements to a negative
value. This is represented by a <code>ge</code> comparison of the register
with constant zero. For this case, GCC will attach a <code>REG_NONNEG</code>
note to the <code>doloop_end</code> insn if it can determine that the register
will be non-negative.
</li></ul>
<p>Since the <code>doloop_end</code> insn is a jump insn that also has an output,
the reload pass does not handle the output operand. Therefore, the
constraint must allow for that operand to be in memory rather than a
register. In the example shown above, that is handled (in the
<code>doloop_end_insn</code> pattern) by using a loop instruction sequence
that can handle memory operands when the memory alternative appears.
</p>
<p>GCC does not check the mode of the loop register operand when generating
the <code>doloop_end</code> pattern. If the pattern is only valid for some
modes but not others, the pattern should be a <code>define_expand</code>
pattern that checks the operand mode in the preparation code, and issues
<code>FAIL</code> if an unsupported mode is found. The example above does
this, since the machine instruction to be used only exists for
<code>HImode</code>.
</p>
<p>If the <code>doloop_end</code> pattern is a <code>define_expand</code>, there must
also be a <code>define_insn</code> or <code>define_insn_and_split</code> matching
the generated pattern. Otherwise, the compiler will fail during loop
optimization.
</p>
<hr>
<div class="header">
<p>
Next: <a href="Insn-Canonicalizations.html#Insn-Canonicalizations" accesskey="n" rel="next">Insn Canonicalizations</a>, Previous: <a href="Jump-Patterns.html#Jump-Patterns" accesskey="p" rel="previous">Jump Patterns</a>, Up: <a href="Machine-Desc.html#Machine-Desc" accesskey="u" rel="up">Machine Desc</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>
|
