OSDN Git Service

PR tree-optimization/9814
[pf3gnuchains/gcc-fork.git] / gcc / doc / tree-ssa.texi
1 @c Copyright (c) 2004, 2005 Free Software Foundation, Inc.
2 @c Free Software Foundation, Inc.
3 @c This is part of the GCC manual.
4 @c For copying conditions, see the file gcc.texi.
5
6 @c ---------------------------------------------------------------------
7 @c Tree SSA
8 @c ---------------------------------------------------------------------
9
10 @node Tree SSA
11 @chapter Analysis and Optimization of GIMPLE Trees
12 @cindex Tree SSA
13 @cindex Optimization infrastructure for GIMPLE
14
15 GCC uses three main intermediate languages to represent the program
16 during compilation: GENERIC, GIMPLE and RTL@.  GENERIC is a
17 language-independent representation generated by each front end.  It
18 is used to serve as an interface between the parser and optimizer.
19 GENERIC is a common representation that is able to represent programs
20 written in all the languages supported by GCC@.
21
22 GIMPLE and RTL are used to optimize the program.  GIMPLE is used for
23 target and language independent optimizations (e.g., inlining,
24 constant propagation, tail call elimination, redundancy elimination,
25 etc).  Much like GENERIC, GIMPLE is a language independent, tree based
26 representation.  However, it differs from GENERIC in that the GIMPLE
27 grammar is more restrictive: expressions contain no more than 3
28 operands (except function calls), it has no control flow structures
29 and expressions with side-effects are only allowed on the right hand
30 side of assignments.  See the chapter describing GENERIC and GIMPLE
31 for more details.
32
33 This chapter describes the data structures and functions used in the
34 GIMPLE optimizers (also known as ``tree optimizers'' or ``middle
35 end'').  In particular, it focuses on all the macros, data structures,
36 functions and programming constructs needed to implement optimization
37 passes for GIMPLE@.
38
39 @menu
40 * GENERIC::             A high-level language-independent representation.
41 * GIMPLE::              A lower-level factored tree representation.
42 * Annotations::         Attributes for statements and variables.
43 * Statement Operands::  Variables referenced by GIMPLE statements.
44 * SSA::                 Static Single Assignment representation.
45 * Alias analysis::      Representing aliased loads and stores.
46 @end menu
47
48 @node GENERIC
49 @section GENERIC
50 @cindex GENERIC
51
52 The purpose of GENERIC is simply to provide a language-independent way of
53 representing an entire function in trees.  To this end, it was necessary to
54 add a few new tree codes to the back end, but most everything was already
55 there.  If you can express it with the codes in @code{gcc/tree.def}, it's
56 GENERIC@.
57
58 Early on, there was a great deal of debate about how to think about
59 statements in a tree IL@.  In GENERIC, a statement is defined as any
60 expression whose value, if any, is ignored.  A statement will always
61 have @code{TREE_SIDE_EFFECTS} set (or it will be discarded), but a
62 non-statement expression may also have side effects.  A
63 @code{CALL_EXPR}, for instance.
64
65 It would be possible for some local optimizations to work on the
66 GENERIC form of a function; indeed, the adapted tree inliner works
67 fine on GENERIC, but the current compiler performs inlining after
68 lowering to GIMPLE (a restricted form described in the next section).
69 Indeed, currently the frontends perform this lowering before handing
70 off to @code{tree_rest_of_compilation}, but this seems inelegant.
71
72 If necessary, a front end can use some language-dependent tree codes
73 in its GENERIC representation, so long as it provides a hook for
74 converting them to GIMPLE and doesn't expect them to work with any
75 (hypothetical) optimizers that run before the conversion to GIMPLE@.
76 The intermediate representation used while parsing C and C++ looks
77 very little like GENERIC, but the C and C++ gimplifier hooks are
78 perfectly happy to take it as input and spit out GIMPLE@.
79
80 @node GIMPLE
81 @section GIMPLE
82 @cindex GIMPLE
83
84 GIMPLE is a simplified subset of GENERIC for use in optimization.  The
85 particular subset chosen (and the name) was heavily influenced by the
86 SIMPLE IL used by the McCAT compiler project at McGill University,
87 though we have made some different choices.  For one thing, SIMPLE
88 doesn't support @code{goto}; a production compiler can't afford that
89 kind of restriction.
90
91 GIMPLE retains much of the structure of the parse trees: lexical
92 scopes are represented as containers, rather than markers.  However,
93 expressions are broken down into a 3-address form, using temporary
94 variables to hold intermediate values.  Also, control structures are
95 lowered to gotos.
96
97 In GIMPLE no container node is ever used for its value; if a
98 @code{COND_EXPR} or @code{BIND_EXPR} has a value, it is stored into a
99 temporary within the controlled blocks, and that temporary is used in
100 place of the container.
101
102 The compiler pass which lowers GENERIC to GIMPLE is referred to as the
103 @samp{gimplifier}.  The gimplifier works recursively, replacing complex
104 statements with sequences of simple statements.
105
106 @c Currently, the only way to
107 @c tell whether or not an expression is in GIMPLE form is by recursively
108 @c examining it; in the future there will probably be a flag to help avoid
109 @c redundant work.  FIXME FIXME
110
111 @menu
112 * Interfaces::
113 * Temporaries::
114 * GIMPLE Expressions::
115 * Statements::
116 * GIMPLE Example::
117 * Rough GIMPLE Grammar::
118 @end menu
119
120 @node Interfaces
121 @subsection Interfaces
122 @cindex gimplification
123
124 The tree representation of a function is stored in
125 @code{DECL_SAVED_TREE}.  It is lowered to GIMPLE by a call to
126 @code{gimplify_function_tree}.
127
128 If a front end wants to include language-specific tree codes in the tree
129 representation which it provides to the back end, it must provide a
130 definition of @code{LANG_HOOKS_GIMPLIFY_EXPR} which knows how to
131 convert the front end trees to GIMPLE@.  Usually such a hook will involve
132 much of the same code for expanding front end trees to RTL@.  This function
133 can return fully lowered GIMPLE, or it can return GENERIC trees and let the
134 main gimplifier lower them the rest of the way; this is often simpler.
135
136 The C and C++ front ends currently convert directly from front end
137 trees to GIMPLE, and hand that off to the back end rather than first
138 converting to GENERIC@.  Their gimplifier hooks know about all the
139 @code{_STMT} nodes and how to convert them to GENERIC forms.  There
140 was some work done on a genericization pass which would run first, but
141 the existence of @code{STMT_EXPR} meant that in order to convert all
142 of the C statements into GENERIC equivalents would involve walking the
143 entire tree anyway, so it was simpler to lower all the way.  This
144 might change in the future if someone writes an optimization pass
145 which would work better with higher-level trees, but currently the
146 optimizers all expect GIMPLE@.
147
148 A front end which wants to use the tree optimizers (and already has
149 some sort of whole-function tree representation) only needs to provide
150 a definition of @code{LANG_HOOKS_GIMPLIFY_EXPR}, call
151 @code{gimplify_function_tree} to lower to GIMPLE, and then hand off to
152 @code{tree_rest_of_compilation} to compile and output the function.
153
154 You can tell the compiler to dump a C-like representation of the GIMPLE
155 form with the flag @option{-fdump-tree-gimple}.
156
157 @node Temporaries
158 @subsection Temporaries
159 @cindex Temporaries
160
161 When gimplification encounters a subexpression which is too complex, it
162 creates a new temporary variable to hold the value of the subexpression,
163 and adds a new statement to initialize it before the current statement.
164 These special temporaries are known as @samp{expression temporaries}, and are
165 allocated using @code{get_formal_tmp_var}.  The compiler tries to
166 always evaluate identical expressions into the same temporary, to simplify
167 elimination of redundant calculations.
168
169 We can only use expression temporaries when we know that it will not be
170 reevaluated before its value is used, and that it will not be otherwise
171 modified@footnote{These restrictions are derived from those in Morgan 4.8.}.
172 Other temporaries can be allocated using
173 @code{get_initialized_tmp_var} or @code{create_tmp_var}.
174
175 Currently, an expression like @code{a = b + 5} is not reduced any
176 further.  We tried converting it to something like
177 @smallexample
178   T1 = b + 5;
179   a = T1;
180 @end smallexample
181 but this bloated the representation for minimal benefit.  However, a
182 variable which must live in memory cannot appear in an expression; its
183 value is explicitly loaded into a temporary first.  Similarly, storing
184 the value of an expression to a memory variable goes through a
185 temporary.
186
187 @node GIMPLE Expressions
188 @subsection Expressions
189 @cindex GIMPLE Expressions
190
191 In general, expressions in GIMPLE consist of an operation and the
192 appropriate number of simple operands; these operands must either be a
193 GIMPLE rvalue (@code{is_gimple_val}), i.e.@: a constant or a register
194 variable.  More complex operands are factored out into temporaries, so
195 that
196 @smallexample
197   a = b + c + d
198 @end smallexample
199 becomes
200 @smallexample
201   T1 = b + c;
202   a = T1 + d;
203 @end smallexample
204
205 The same rule holds for arguments to a @code{CALL_EXPR}.
206
207 The target of an assignment is usually a variable, but can also be an
208 @code{INDIRECT_REF} or a compound lvalue as described below.
209
210 @menu
211 * Compound Expressions::
212 * Compound Lvalues::
213 * Conditional Expressions::
214 * Logical Operators::
215 @end menu
216
217 @node Compound Expressions
218 @subsubsection Compound Expressions
219 @cindex Compound Expressions
220
221 The left-hand side of a C comma expression is simply moved into a separate
222 statement.
223
224 @node Compound Lvalues
225 @subsubsection Compound Lvalues
226 @cindex Compound Lvalues
227
228 Currently compound lvalues involving array and structure field references
229 are not broken down; an expression like @code{a.b[2] = 42} is not reduced
230 any further (though complex array subscripts are).  This restriction is a
231 workaround for limitations in later optimizers; if we were to convert this
232 to
233
234 @smallexample
235   T1 = &a.b;
236   T1[2] = 42;
237 @end smallexample
238
239 alias analysis would not remember that the reference to @code{T1[2]} came
240 by way of @code{a.b}, so it would think that the assignment could alias
241 another member of @code{a}; this broke @code{struct-alias-1.c}.  Future
242 optimizer improvements may make this limitation unnecessary.
243
244 @node Conditional Expressions
245 @subsubsection Conditional Expressions
246 @cindex Conditional Expressions
247
248 A C @code{?:} expression is converted into an @code{if} statement with
249 each branch assigning to the same temporary.  So,
250
251 @smallexample
252   a = b ? c : d;
253 @end smallexample
254 becomes
255 @smallexample
256   if (b)
257     T1 = c;
258   else
259     T1 = d;
260   a = T1;
261 @end smallexample
262
263 Tree level if-conversion pass re-introduces @code{?:} expression, if appropriate.
264 It is used to vectorize loops with conditions using vector conditional operations.
265
266 Note that in GIMPLE, @code{if} statements are also represented using
267 @code{COND_EXPR}, as described below.
268
269 @node Logical Operators
270 @subsubsection Logical Operators
271 @cindex Logical Operators
272
273 Except when they appear in the condition operand of a @code{COND_EXPR},
274 logical `and' and `or' operators are simplified as follows:
275 @code{a = b && c} becomes
276
277 @smallexample
278   T1 = (bool)b;
279   if (T1)
280     T1 = (bool)c;
281   a = T1;
282 @end smallexample
283
284 Note that @code{T1} in this example cannot be an expression temporary,
285 because it has two different assignments.
286
287 @node Statements
288 @subsection Statements
289 @cindex Statements
290
291 Most statements will be assignment statements, represented by
292 @code{MODIFY_EXPR}.  A @code{CALL_EXPR} whose value is ignored can
293 also be a statement.  No other C expressions can appear at statement level;
294 a reference to a volatile object is converted into a @code{MODIFY_EXPR}.
295 In GIMPLE form, type of @code{MODIFY_EXPR} is not meaningful.  Instead, use type
296 of LHS or RHS@.
297
298 There are also several varieties of complex statements.
299
300 @menu
301 * Blocks::
302 * Statement Sequences::
303 * Empty Statements::
304 * Loops::
305 * Selection Statements::
306 * Jumps::
307 * Cleanups::
308 * GIMPLE Exception Handling::
309 @end menu
310
311 @node Blocks
312 @subsubsection Blocks
313 @cindex Blocks
314
315 Block scopes and the variables they declare in GENERIC and GIMPLE are
316 expressed using the @code{BIND_EXPR} code, which in previous versions of
317 GCC was primarily used for the C statement-expression extension.
318
319 Variables in a block are collected into @code{BIND_EXPR_VARS} in
320 declaration order.  Any runtime initialization is moved out of
321 @code{DECL_INITIAL} and into a statement in the controlled block.  When
322 gimplifying from C or C++, this initialization replaces the
323 @code{DECL_STMT}.
324
325 Variable-length arrays (VLAs) complicate this process, as their size often
326 refers to variables initialized earlier in the block.  To handle this, we
327 currently split the block at that point, and move the VLA into a new, inner
328 @code{BIND_EXPR}.  This strategy may change in the future.
329
330 @code{DECL_SAVED_TREE} for a GIMPLE function will always be a
331 @code{BIND_EXPR} which contains declarations for the temporary variables
332 used in the function.
333
334 A C++ program will usually contain more @code{BIND_EXPR}s than there are
335 syntactic blocks in the source code, since several C++ constructs have
336 implicit scopes associated with them.  On the other hand, although the C++
337 front end uses pseudo-scopes to handle cleanups for objects with
338 destructors, these don't translate into the GIMPLE form; multiple
339 declarations at the same level use the same @code{BIND_EXPR}.
340
341 @node Statement Sequences
342 @subsubsection Statement Sequences
343 @cindex Statement Sequences
344
345 Multiple statements at the same nesting level are collected into a
346 @code{STATEMENT_LIST}.  Statement lists are modified and traversed
347 using the interface in @samp{tree-iterator.h}.
348
349 @node Empty Statements
350 @subsubsection Empty Statements
351 @cindex Empty Statements
352
353 Whenever possible, statements with no effect are discarded.  But if they
354 are nested within another construct which cannot be discarded for some
355 reason, they are instead replaced with an empty statement, generated by
356 @code{build_empty_stmt}.  Initially, all empty statements were shared,
357 after the pattern of the Java front end, but this caused a lot of trouble in
358 practice.
359
360 An empty statement is represented as @code{(void)0}.
361
362 @node Loops
363 @subsubsection Loops
364 @cindex Loops
365
366 At one time loops were expressed in GIMPLE using @code{LOOP_EXPR}, but
367 now they are lowered to explicit gotos.
368
369 @node Selection Statements
370 @subsubsection Selection Statements
371 @cindex Selection Statements
372
373 A simple selection statement, such as the C @code{if} statement, is
374 expressed in GIMPLE using a void @code{COND_EXPR}.  If only one branch is
375 used, the other is filled with an empty statement.
376
377 Normally, the condition expression is reduced to a simple comparison.  If
378 it is a shortcut (@code{&&} or @code{||}) expression, however, we try to
379 break up the @code{if} into multiple @code{if}s so that the implied shortcut
380 is taken directly, much like the transformation done by @code{do_jump} in
381 the RTL expander.
382
383 A @code{SWITCH_EXPR} in GIMPLE contains the condition and a
384 @code{TREE_VEC} of @code{CASE_LABEL_EXPR}s describing the case values
385 and corresponding @code{LABEL_DECL}s to jump to.  The body of the
386 @code{switch} is moved after the @code{SWITCH_EXPR}.
387
388 @node Jumps
389 @subsubsection Jumps
390 @cindex Jumps
391
392 Other jumps are expressed by either @code{GOTO_EXPR} or @code{RETURN_EXPR}.
393
394 The operand of a @code{GOTO_EXPR} must be either a label or a variable
395 containing the address to jump to.
396
397 The operand of a @code{RETURN_EXPR} is either @code{NULL_TREE} or a
398 @code{MODIFY_EXPR} which sets the return value.  It would be nice to
399 move the @code{MODIFY_EXPR} into a separate statement, but the special
400 return semantics in @code{expand_return} make that difficult.  It may
401 still happen in the future, perhaps by moving most of that logic into
402 @code{expand_assignment}.
403
404 @node Cleanups
405 @subsubsection Cleanups
406 @cindex Cleanups
407
408 Destructors for local C++ objects and similar dynamic cleanups are
409 represented in GIMPLE by a @code{TRY_FINALLY_EXPR}.  When the controlled
410 block exits, the cleanup is run.
411
412 @code{TRY_FINALLY_EXPR} complicates the flow graph, since the cleanup
413 needs to appear on every edge out of the controlled block; this
414 reduces the freedom to move code across these edges.  Therefore, the
415 EH lowering pass which runs before most of the optimization passes
416 eliminates these expressions by explicitly adding the cleanup to each
417 edge.
418
419 @node GIMPLE Exception Handling
420 @subsubsection Exception Handling
421 @cindex GIMPLE Exception Handling
422
423 Other exception handling constructs are represented using
424 @code{TRY_CATCH_EXPR}.  The handler operand of a @code{TRY_CATCH_EXPR}
425 can be a normal statement to be executed if the controlled block throws an
426 exception, or it can have one of two special forms:
427
428 @enumerate
429 @item A @code{CATCH_EXPR} executes its handler if the thrown exception
430   matches one of the allowed types.  Multiple handlers can be
431   expressed by a sequence of @code{CATCH_EXPR} statements.
432 @item An @code{EH_FILTER_EXPR} executes its handler if the thrown
433   exception does not match one of the allowed types.
434 @end enumerate
435
436 Currently throwing an exception is not directly represented in GIMPLE,
437 since it is implemented by calling a function.  At some point in the future
438 we will want to add some way to express that the call will throw an
439 exception of a known type.
440
441 Just before running the optimizers, the compiler lowers the high-level
442 EH constructs above into a set of @samp{goto}s, magic labels, and EH
443 regions.  Continuing to unwind at the end of a cleanup is represented
444 with a @code{RESX_EXPR}.
445
446 @node GIMPLE Example
447 @subsection GIMPLE Example
448 @cindex GIMPLE Example
449
450 @smallexample
451 struct A @{ A(); ~A(); @};
452
453 int i;
454 int g();
455 void f()
456 @{
457   A a;
458   int j = (--i, i ? 0 : 1);
459
460   for (int x = 42; x > 0; --x)
461     @{
462       i += g()*4 + 32;
463     @}
464 @}
465 @end smallexample
466
467 becomes
468
469 @smallexample
470 void f()
471 @{
472   int i.0;
473   int T.1;
474   int iftmp.2;
475   int T.3;
476   int T.4;
477   int T.5;
478   int T.6;
479
480   @{
481     struct A a;
482     int j;
483
484     __comp_ctor (&a);
485     try
486       @{
487         i.0 = i;
488         T.1 = i.0 - 1;
489         i = T.1;
490         i.0 = i;
491         if (i.0 == 0)
492           iftmp.2 = 1;
493         else
494           iftmp.2 = 0;
495         j = iftmp.2;
496         @{
497           int x;
498
499           x = 42;
500           goto test;
501           loop:;
502
503           T.3 = g ();
504           T.4 = T.3 * 4;
505           i.0 = i;
506           T.5 = T.4 + i.0;
507           T.6 = T.5 + 32;
508           i = T.6;
509           x = x - 1;
510
511           test:;
512           if (x > 0)
513             goto loop;
514           else
515             goto break_;
516           break_:;
517         @}
518       @}
519     finally
520       @{
521         __comp_dtor (&a);
522       @}
523   @}
524 @}
525 @end smallexample
526
527 @node Rough GIMPLE Grammar
528 @subsection Rough GIMPLE Grammar
529 @cindex Rough GIMPLE Grammar
530
531 @smallexample
532    function     : FUNCTION_DECL
533                         DECL_SAVED_TREE -> compound-stmt
534
535    compound-stmt: STATEMENT_LIST
536                         members -> stmt
537
538    stmt         : block
539                 | if-stmt
540                 | switch-stmt
541                 | goto-stmt
542                 | return-stmt
543                 | resx-stmt
544                 | label-stmt
545                 | try-stmt
546                 | modify-stmt
547                 | call-stmt
548
549    block        : BIND_EXPR
550                         BIND_EXPR_VARS -> chain of DECLs
551                         BIND_EXPR_BLOCK -> BLOCK
552                         BIND_EXPR_BODY -> compound-stmt
553
554    if-stmt      : COND_EXPR
555                         op0 -> condition
556                         op1 -> compound-stmt
557                         op2 -> compound-stmt
558
559    switch-stmt  : SWITCH_EXPR
560                         op0 -> val
561                         op1 -> NULL
562                         op2 -> TREE_VEC of CASE_LABEL_EXPRs
563                             The CASE_LABEL_EXPRs are sorted by CASE_LOW,
564                             and default is last.
565
566    goto-stmt    : GOTO_EXPR
567                         op0 -> LABEL_DECL | val
568
569    return-stmt  : RETURN_EXPR
570                         op0 -> return-value
571
572    return-value : NULL
573                 | RESULT_DECL
574                 | MODIFY_EXPR
575                         op0 -> RESULT_DECL
576                         op1 -> lhs
577
578    resx-stmt    : RESX_EXPR
579
580    label-stmt   : LABEL_EXPR
581                         op0 -> LABEL_DECL
582
583    try-stmt     : TRY_CATCH_EXPR
584                         op0 -> compound-stmt
585                         op1 -> handler
586                 | TRY_FINALLY_EXPR
587                         op0 -> compound-stmt
588                         op1 -> compound-stmt
589
590    handler      : catch-seq
591                 | EH_FILTER_EXPR
592                 | compound-stmt
593
594    catch-seq    : STATEMENT_LIST
595                         members -> CATCH_EXPR
596
597    modify-stmt  : MODIFY_EXPR
598                         op0 -> lhs
599                         op1 -> rhs
600
601    call-stmt    : CALL_EXPR
602                         op0 -> val | OBJ_TYPE_REF
603                         op1 -> call-arg-list
604
605    call-arg-list: TREE_LIST
606                         members -> lhs | CONST
607
608    addr-expr-arg: ID
609                 | compref
610
611    addressable  : addr-expr-arg
612                 | indirectref
613
614    with-size-arg: addressable
615                 | call-stmt
616
617    indirectref  : INDIRECT_REF
618                         op0 -> val
619
620    lhs          : addressable
621                 | bitfieldref
622                 | WITH_SIZE_EXPR
623                         op0 -> with-size-arg
624                         op1 -> val
625
626    min-lval     : ID
627                 | indirectref
628
629    bitfieldref  : BIT_FIELD_REF
630                         op0 -> inner-compref
631                         op1 -> CONST
632                         op2 -> var
633
634    compref      : inner-compref
635                 | REALPART_EXPR
636                         op0 -> inner-compref
637                 | IMAGPART_EXPR
638                         op0 -> inner-compref
639
640    inner-compref: min-lval
641                 | COMPONENT_REF
642                         op0 -> inner-compref
643                         op1 -> FIELD_DECL
644                         op2 -> val
645                 | ARRAY_REF
646                         op0 -> inner-compref
647                         op1 -> val
648                         op2 -> val
649                         op3 -> val
650                 | ARRAY_RANGE_REF
651                         op0 -> inner-compref
652                         op1 -> val
653                         op2 -> val
654                         op3 -> val
655                 | VIEW_CONVERT_EXPR
656                         op0 -> inner-compref
657
658    condition    : val
659                 | RELOP
660                         op0 -> val
661                         op1 -> val
662
663    val          : ID
664                 | CONST
665
666    rhs          : lhs
667                 | CONST
668                 | call-stmt
669                 | ADDR_EXPR
670                         op0 -> addr-expr-arg
671                 | UNOP
672                         op0 -> val
673                 | BINOP
674                         op0 -> val
675                         op1 -> val
676                 | RELOP
677                         op0 -> val
678                         op1 -> val
679 @end smallexample
680
681 @node Annotations
682 @section Annotations
683 @cindex annotations
684
685 The optimizers need to associate attributes with statements and
686 variables during the optimization process.  For instance, we need to
687 know what basic block a statement belongs to or whether a variable
688 has aliases.  All these attributes are stored in data structures
689 called annotations which are then linked to the field @code{ann} in
690 @code{struct tree_common}.
691
692 Presently, we define annotations for statements (@code{stmt_ann_t}),
693 variables (@code{var_ann_t}) and SSA names (@code{ssa_name_ann_t}).
694 Annotations are defined and documented in @file{tree-flow.h}.
695
696
697 @node Statement Operands
698 @section Statement Operands
699 @cindex operands
700 @cindex virtual operands
701 @cindex real operands
702 @findex update_stmt
703
704 Almost every GIMPLE statement will contain a reference to a variable
705 or memory location.  Since statements come in different shapes and
706 sizes, their operands are going to be located at various spots inside
707 the statement's tree.  To facilitate access to the statement's
708 operands, they are organized into lists associated inside each
709 statement's annotation.  Each element in an operand list is a pointer
710 to a @code{VAR_DECL}, @code{PARM_DECL} or @code{SSA_NAME} tree node.
711 This provides a very convenient way of examining and replacing
712 operands.
713
714 Data flow analysis and optimization is done on all tree nodes
715 representing variables.  Any node for which @code{SSA_VAR_P} returns
716 nonzero is considered when scanning statement operands.  However, not
717 all @code{SSA_VAR_P} variables are processed in the same way.  For the
718 purposes of optimization, we need to distinguish between references to
719 local scalar variables and references to globals, statics, structures,
720 arrays, aliased variables, etc.  The reason is simple, the compiler
721 can gather complete data flow information for a local scalar.  On the
722 other hand, a global variable may be modified by a function call, it
723 may not be possible to keep track of all the elements of an array or
724 the fields of a structure, etc.
725
726 The operand scanner gathers two kinds of operands: @dfn{real} and
727 @dfn{virtual}.  An operand for which @code{is_gimple_reg} returns true
728 is considered real, otherwise it is a virtual operand.  We also
729 distinguish between uses and definitions.  An operand is used if its
730 value is loaded by the statement (e.g., the operand at the RHS of an
731 assignment).  If the statement assigns a new value to the operand, the
732 operand is considered a definition (e.g., the operand at the LHS of
733 an assignment).
734
735 Virtual and real operands also have very different data flow
736 properties.  Real operands are unambiguous references to the
737 full object that they represent.  For instance, given
738
739 @smallexample
740 @{
741   int a, b;
742   a = b
743 @}
744 @end smallexample
745
746 Since @code{a} and @code{b} are non-aliased locals, the statement
747 @code{a = b} will have one real definition and one real use because
748 variable @code{b} is completely modified with the contents of
749 variable @code{a}.  Real definition are also known as @dfn{killing
750 definitions}.  Similarly, the use of @code{a} reads all its bits.
751
752 In contrast, virtual operands are used with variables that can have
753 a partial or ambiguous reference.  This includes structures, arrays,
754 globals, and aliased variables.  In these cases, we have two types of
755 definitions.  For globals, structures, and arrays, we can determine from
756 a statement whether a variable of these types has a killing definition.
757 If the variable does, then the statement is marked as having a
758 @dfn{must definition} of that variable.  However, if a statement is only
759 defining a part of the variable (i.e.@: a field in a structure), or if we
760 know that a statement might define the variable but we cannot say for sure,
761 then we mark that statement as having a @dfn{may definition}.  For
762 instance, given
763
764 @smallexample
765 @{
766   int a, b, *p;
767
768   if (...)
769     p = &a;
770   else
771     p = &b;
772   *p = 5;
773   return *p;
774 @}
775 @end smallexample
776
777 The assignment @code{*p = 5} may be a definition of @code{a} or
778 @code{b}.  If we cannot determine statically where @code{p} is
779 pointing to at the time of the store operation, we create virtual
780 definitions to mark that statement as a potential definition site for
781 @code{a} and @code{b}.  Memory loads are similarly marked with virtual
782 use operands.  Virtual operands are shown in tree dumps right before
783 the statement that contains them.  To request a tree dump with virtual
784 operands, use the @option{-vops} option to @option{-fdump-tree}:
785
786 @smallexample
787 @{
788   int a, b, *p;
789
790   if (...)
791     p = &a;
792   else
793     p = &b;
794   # a = V_MAY_DEF <a>
795   # b = V_MAY_DEF <b>
796   *p = 5;
797
798   # VUSE <a>
799   # VUSE <b>
800   return *p;
801 @}
802 @end smallexample
803
804 Notice that @code{V_MAY_DEF} operands have two copies of the referenced
805 variable.  This indicates that this is not a killing definition of
806 that variable.  In this case we refer to it as a @dfn{may definition}
807 or @dfn{aliased store}.  The presence of the second copy of the
808 variable in the @code{V_MAY_DEF} operand will become important when the
809 function is converted into SSA form.  This will be used to link all
810 the non-killing definitions to prevent optimizations from making
811 incorrect assumptions about them.
812
813 Operands are updated as soon as the statement is finished via a call
814 to @code{update_stmt}.  If statement elements are changed via
815 @code{SET_USE} or @code{SET_DEF}, then no further action is required
816 (ie, those macros take care of updating the statement).  If changes
817 are made by manipulating the statement's tree directly, then a call
818 must be made to @code{update_stmt} when complete.  Calling one of the
819 @code{bsi_insert} routines or @code{bsi_replace} performs an implicit
820 call to @code{update_stmt}.
821
822 @subsection Operand Iterators And Access Routines
823 @cindex Operand Iterators 
824 @cindex Operand Access Routines
825
826 Operands are collected by @file{tree-ssa-operands.c}.  They are stored
827 inside each statement's annotation and can be accessed through either the
828 operand iterators or an access routine.
829
830 The following access routines are available for examining operands:
831
832 @enumerate
833 @item @code{SINGLE_SSA_@{USE,DEF,TREE@}_OPERAND}: These accessors will return 
834 NULL unless there is exactly one operand matching the specified flags.  If 
835 there is exactly one operand, the operand is returned as either a @code{tree}, 
836 @code{def_operand_p}, or @code{use_operand_p}.
837
838 @smallexample
839 tree t = SINGLE_SSA_TREE_OPERAND (stmt, flags);
840 use_operand_p u = SINGLE_SSA_USE_OPERAND (stmt, SSA_ALL_VIRTUAL_USES);
841 def_operand_p d = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_ALL_DEFS);
842 @end smallexample
843
844 @item @code{ZERO_SSA_OPERANDS}: This macro returns true if there are no 
845 operands matching the specified flags.
846
847 @smallexample
848 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
849   return;
850 @end smallexample
851
852 @item @code{NUM_SSA_OPERANDS}: This macro Returns the number of operands 
853 matching 'flags'.  This actually executes a loop to perform the count, so 
854 only use this if it is really needed.
855
856 @smallexample
857 int count = NUM_SSA_OPERANDS (stmt, flags)
858 @end smallexample
859 @end enumerate
860
861
862 If you wish to iterate over some or all operands, use the
863 @code{FOR_EACH_SSA_@{USE,DEF,TREE@}_OPERAND} iterator.  For example, to print
864 all the operands for a statement:
865
866 @smallexample
867 void
868 print_ops (tree stmt)
869 @{
870   ssa_op_iter;
871   tree var;
872
873   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_OPERANDS)
874     print_generic_expr (stderr, var, TDF_SLIM);
875 @}
876 @end smallexample
877
878
879 How to choose the appropriate iterator:
880
881 @enumerate
882 @item Determine whether you are need to see the operand pointers, or just the
883     trees, and choose the appropriate macro:
884
885 @smallexample
886 Need            Macro:
887 ----            -------
888 use_operand_p   FOR_EACH_SSA_USE_OPERAND
889 def_operand_p   FOR_EACH_SSA_DEF_OPERAND
890 tree            FOR_EACH_SSA_TREE_OPERAND
891 @end smallexample
892
893 @item You need to declare a variable of the type you are interested
894     in, and an ssa_op_iter structure which serves as the loop
895     controlling variable.
896
897 @item Determine which operands you wish to use, and specify the flags of
898     those you are interested in.  They are documented in
899     @file{tree-ssa-operands.h}:
900
901 @smallexample
902 #define SSA_OP_USE              0x01    /* @r{Real USE operands.}  */
903 #define SSA_OP_DEF              0x02    /* @r{Real DEF operands.}  */
904 #define SSA_OP_VUSE             0x04    /* @r{VUSE operands.}  */
905 #define SSA_OP_VMAYUSE          0x08    /* @r{USE portion of V_MAY_DEFS.}  */
906 #define SSA_OP_VMAYDEF          0x10    /* @r{DEF portion of V_MAY_DEFS.}  */
907 #define SSA_OP_VMUSTDEF         0x20    /* @r{V_MUST_DEF definitions.}  */
908
909 /* @r{These are commonly grouped operand flags.}  */
910 #define SSA_OP_VIRTUAL_USES     (SSA_OP_VUSE | SSA_OP_VMAYUSE)
911 #define SSA_OP_VIRTUAL_DEFS     (SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF)
912 #define SSA_OP_ALL_USES         (SSA_OP_VIRTUAL_USES | SSA_OP_USE)
913 #define SSA_OP_ALL_DEFS         (SSA_OP_VIRTUAL_DEFS | SSA_OP_DEF)
914 #define SSA_OP_ALL_OPERANDS     (SSA_OP_ALL_USES | SSA_OP_ALL_DEFS)
915 @end smallexample
916 @end enumerate
917
918 So if you want to look at the use pointers for all the @code{USE} and
919 @code{VUSE} operands, you would do something like:
920
921 @smallexample
922   use_operand_p use_p;
923   ssa_op_iter iter;
924
925   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, (SSA_OP_USE | SSA_OP_VUSE))
926     @{
927       process_use_ptr (use_p);
928     @}
929 @end smallexample
930
931 The @code{TREE} macro is basically the same as the @code{USE} and
932 @code{DEF} macros, only with the use or def dereferenced via
933 @code{USE_FROM_PTR (use_p)} and @code{DEF_FROM_PTR (def_p)}.  Since we
934 aren't using operand pointers, use and defs flags can be mixed.
935
936 @smallexample
937   tree var;
938   ssa_op_iter iter;
939
940   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_VUSE | SSA_OP_VMUSTDEF)
941     @{
942        print_generic_expr (stderr, var, TDF_SLIM);
943     @}
944 @end smallexample
945
946 @code{V_MAY_DEF}s are broken into two flags, one for the
947 @code{DEF} portion (@code{SSA_OP_VMAYDEF}) and one for the USE portion
948 (@code{SSA_OP_VMAYUSE}).  If all you want to look at are the
949 @code{V_MAY_DEF}s together, there is a fourth iterator macro for this,
950 which returns both a def_operand_p and a use_operand_p for each
951 @code{V_MAY_DEF} in the statement.  Note that you don't need any flags for
952 this one.
953
954 @smallexample
955   use_operand_p use_p;
956   def_operand_p def_p;
957   ssa_op_iter iter;
958
959   FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
960     @{
961       my_code;
962     @}
963 @end smallexample
964
965 @code{V_MUST_DEF}s are broken into two flags, one for the
966 @code{DEF} portion (@code{SSA_OP_VMUSTDEF}) and one for the kill portion
967 (@code{SSA_OP_VMUSTKILL}).  If all you want to look at are the
968 @code{V_MUST_DEF}s together, there is a fourth iterator macro for this,
969 which returns both a def_operand_p and a use_operand_p for each
970 @code{V_MUST_DEF} in the statement.  Note that you don't need any flags for
971 this one.
972
973 @smallexample
974   use_operand_p kill_p;
975   def_operand_p def_p;
976   ssa_op_iter iter;
977
978   FOR_EACH_SSA_MUSTDEF_OPERAND (def_p, kill_p, stmt, iter)
979     @{
980       my_code;
981     @}
982 @end smallexample
983
984
985 There are many examples in the code as well, as well as the
986 documentation in @file{tree-ssa-operands.h}.
987
988 There are also a couple of variants on the stmt iterators regarding PHI
989 nodes.
990
991 @code{FOR_EACH_PHI_ARG} Works exactly like 
992 @code{FOR_EACH_SSA_USE_OPERAND}, except it works over @code{PHI} arguments 
993 instead of statement operands.
994
995 @smallexample
996 /* Look at every virtual PHI use.  */
997 FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_VIRTUAL_USES)
998 @{
999    my_code;
1000 @}
1001
1002 /* Look at every real PHI use.  */
1003 FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_USES)
1004   my_code;
1005
1006 /* Look at every every PHI use.  */
1007 FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_ALL_USES)
1008   my_code;
1009 @end smallexample
1010
1011 @code{FOR_EACH_PHI_OR_STMT_@{USE,DEF@}} works exactly like 
1012 @code{FOR_EACH_SSA_@{USE,DEF@}_OPERAND}, except it will function on
1013 either a statement or a @code{PHI} node.  These should be used when it is
1014 appropriate but they are not quite as efficient as the individual 
1015 @code{FOR_EACH_PHI} and @code{FOR_EACH_SSA} routines.
1016
1017 @smallexample
1018 FOR_EACH_PHI_OR_STMT_USE (use_operand_p, stmt, iter, flags)
1019   @{
1020      my_code;
1021   @}
1022
1023 FOR_EACH_PHI_OR_STMT_DEF (def_operand_p, phi, iter, flags)
1024   @{
1025      my_code;
1026   @}
1027 @end smallexample
1028
1029 @subsection Immediate Uses
1030 @cindex Immediate Uses
1031
1032 Immediate use information is now always available.  Using the immediate use 
1033 iterators, you may examine every use of any @code{SSA_NAME}. For instance,
1034 to change each use of @code{ssa_var} to @code{ssa_var2}:
1035
1036 @smallexample
1037   use_operand_p imm_use_p;
1038   imm_use_iterator iterator;
1039   tree ssa_var
1040
1041   FOR_EACH_IMM_USE_SAFE (imm_use_p, iterator, ssa_var)
1042     SET_USE (imm_use_p, ssa_var_2);
1043 @end smallexample
1044
1045 There are 2 iterators which can be used. @code{FOR_EACH_IMM_USE_FAST} is used 
1046 when the immediate uses are not changed, ie. you are looking at the uses, but 
1047 not setting them.  
1048
1049 If they do get changed, then care must be taken that things are not changed 
1050 under the iterators, so use the @code{FOR_EACH_IMM_USE_SAFE} iterator.  It 
1051 attempts to preserve the sanity of the use list by moving an iterator element
1052 through the use list, preventing insertions and deletions in the list from
1053 resulting in invalid pointers.  This is a little slower since it adds a
1054 placeholder element and moves it through the list.  This element must be 
1055 also be removed if the loop is terminated early.  A macro 
1056 (@code{BREAK_FROM SAFE_IMM_USE}) is provided for this:
1057
1058 @smallexample
1059   FOR_EACH_IMM_USE_SAFE (use_p, iter, var)
1060     @{
1061       if (var == last_var)
1062         BREAK_FROM_SAFE_IMM_USE (iter);
1063       else
1064         SET_USE (use_p, var2);
1065     @}
1066 @end smallexample
1067
1068 There are checks in @code{verify_ssa} which verify that the immediate use list
1069 is up to date, as well as checking that an optimization didn't break from the 
1070 loop without using this macro.  It is safe to simply 'break'; from a 
1071 @code{FOR_EACH_IMM_USE_FAST} traverse.
1072
1073 Some useful functions and macros:
1074 @enumerate
1075 @item  @code{has_zero_uses (ssa_var)} : Returns true if there are no uses of
1076 @code{ssa_var}.
1077 @item   @code{has_single_use (ssa_var)} : Returns true if there is only a 
1078 single use of @code{ssa_var}.
1079 @item   @code{single_imm_use (ssa_var, use_operand_p *ptr, tree *stmt)} :
1080 Returns true if there is only a single use of @code{ssa_var}, and also returns
1081 the use pointer and statement it occurs in in the second and third parameters.
1082 @item   @code{num_imm_uses (ssa_var)} : Returns the number of immediate uses of
1083 @code{ssa_var}. It is better not to use this if possible since it simply
1084 utilizes a loop to count the uses.
1085 @item  @code{PHI_ARG_INDEX_FROM_USE (use_p)} : Given a use within a @code{PHI}
1086 node, return the index number for the use.  An assert is triggered if the use
1087 isn't located in a @code{PHI} node.
1088 @item  @code{USE_STMT (use_p)} : Return the statement a use occurs in.
1089 @end enumerate
1090
1091 Note that uses are not put into an immediate use list until their statement is
1092 actually inserted into the instruction stream via a @code{bsi_*} routine.  
1093
1094 It is also still possible to utilize lazy updating of statements, but this 
1095 should be used only when absolutely required.  Both alias analysis and the 
1096 dominator optimizations currently do this.  
1097
1098 When lazy updating is being used, the immediate use information is out of date 
1099 and cannot be used reliably.  Lazy updating is achieved by simply marking
1100 statements modified via calls to @code{mark_stmt_modified} instead of 
1101 @code{update_stmt}.  When lazy updating is no longer required, all the 
1102 modified statements must have @code{update_stmt} called in order to bring them 
1103 up to date.  This must be done before the optimization is finished, or 
1104 @code{verify_ssa} will trigger an abort.
1105
1106 This is done with a simple loop over the instruction stream:
1107 @smallexample
1108   block_stmt_iterator bsi;
1109   basic_block bb;
1110   FOR_EACH_BB (bb)
1111     @{
1112       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1113         update_stmt_if_modified (bsi_stmt (bsi));
1114     @}
1115 @end smallexample
1116
1117 @node SSA
1118 @section Static Single Assignment
1119 @cindex SSA
1120 @cindex static single assignment
1121
1122 Most of the tree optimizers rely on the data flow information provided
1123 by the Static Single Assignment (SSA) form.  We implement the SSA form
1124 as described in @cite{R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and
1125 K. Zadeck.  Efficiently Computing Static Single Assignment Form and the
1126 Control Dependence Graph.  ACM Transactions on Programming Languages
1127 and Systems, 13(4):451-490, October 1991}.
1128
1129 The SSA form is based on the premise that program variables are
1130 assigned in exactly one location in the program.  Multiple assignments
1131 to the same variable create new versions of that variable.  Naturally,
1132 actual programs are seldom in SSA form initially because variables
1133 tend to be assigned multiple times.  The compiler modifies the program
1134 representation so that every time a variable is assigned in the code,
1135 a new version of the variable is created.  Different versions of the
1136 same variable are distinguished by subscripting the variable name with
1137 its version number.  Variables used in the right-hand side of
1138 expressions are renamed so that their version number matches that of
1139 the most recent assignment.
1140
1141 We represent variable versions using @code{SSA_NAME} nodes.  The
1142 renaming process in @file{tree-ssa.c} wraps every real and
1143 virtual operand with an @code{SSA_NAME} node which contains
1144 the version number and the statement that created the
1145 @code{SSA_NAME}.  Only definitions and virtual definitions may
1146 create new @code{SSA_NAME} nodes.
1147
1148 Sometimes, flow of control makes it impossible to determine what is the
1149 most recent version of a variable.  In these cases, the compiler
1150 inserts an artificial definition for that variable called
1151 @dfn{PHI function} or @dfn{PHI node}.  This new definition merges
1152 all the incoming versions of the variable to create a new name
1153 for it.  For instance,
1154
1155 @smallexample
1156 if (...)
1157   a_1 = 5;
1158 else if (...)
1159   a_2 = 2;
1160 else
1161   a_3 = 13;
1162
1163 # a_4 = PHI <a_1, a_2, a_3>
1164 return a_4;
1165 @end smallexample
1166
1167 Since it is not possible to determine which of the three branches
1168 will be taken at runtime, we don't know which of @code{a_1},
1169 @code{a_2} or @code{a_3} to use at the return statement.  So, the
1170 SSA renamer creates a new version @code{a_4} which is assigned
1171 the result of ``merging'' @code{a_1}, @code{a_2} and @code{a_3}.
1172 Hence, PHI nodes mean ``one of these operands.  I don't know
1173 which''.
1174
1175 The following macros can be used to examine PHI nodes
1176
1177 @defmac PHI_RESULT (@var{phi})
1178 Returns the @code{SSA_NAME} created by PHI node @var{phi} (i.e.,
1179 @var{phi}'s LHS)@.
1180 @end defmac
1181
1182 @defmac PHI_NUM_ARGS (@var{phi})
1183 Returns the number of arguments in @var{phi}.  This number is exactly
1184 the number of incoming edges to the basic block holding @var{phi}@.
1185 @end defmac
1186
1187 @defmac PHI_ARG_ELT (@var{phi}, @var{i})
1188 Returns a tuple representing the @var{i}th argument of @var{phi}@.
1189 Each element of this tuple contains an @code{SSA_NAME} @var{var} and
1190 the incoming edge through which @var{var} flows.
1191 @end defmac
1192
1193 @defmac PHI_ARG_EDGE (@var{phi}, @var{i})
1194 Returns the incoming edge for the @var{i}th argument of @var{phi}.
1195 @end defmac
1196
1197 @defmac PHI_ARG_DEF (@var{phi}, @var{i})
1198 Returns the @code{SSA_NAME} for the @var{i}th argument of @var{phi}.
1199 @end defmac
1200
1201
1202 @subsection Preserving the SSA form
1203 @findex update_ssa
1204 @cindex preserving SSA form
1205 Some optimization passes make changes to the function that
1206 invalidate the SSA property.  This can happen when a pass has
1207 added new symbols or changed the program so that variables that
1208 were previously aliased aren't anymore.  Whenever something like this
1209 happens, the affected symbols must be renamed into SSA form again.  
1210 Transformations that emit new code or replicate existing statements
1211 will also need to update the SSA form@.
1212
1213 Since GCC implements two different SSA forms for register and virtual
1214 variables, keeping the SSA form up to date depends on whether you are
1215 updating register or virtual names.  In both cases, the general idea
1216 behind incremental SSA updates is similar: when new SSA names are
1217 created, they typically are meant to replace other existing names in
1218 the program@.
1219
1220 For instance, given the following code:
1221
1222 @smallexample
1223      1  L0:
1224      2  x_1 = PHI (0, x_5)
1225      3  if (x_1 < 10)
1226      4    if (x_1 > 7)
1227      5      y_2 = 0
1228      6    else
1229      7      y_3 = x_1 + x_7
1230      8    endif
1231      9    x_5 = x_1 + 1
1232      10   goto L0;
1233      11 endif
1234 @end smallexample
1235
1236 Suppose that we insert new names @code{x_10} and @code{x_11} (lines
1237 @code{4} and @code{8})@.
1238
1239 @smallexample
1240      1  L0:
1241      2  x_1 = PHI (0, x_5)
1242      3  if (x_1 < 10)
1243      4    x_10 = ...
1244      5    if (x_1 > 7)
1245      6      y_2 = 0
1246      7    else
1247      8      x_11 = ...
1248      9      y_3 = x_1 + x_7
1249      10   endif
1250      11   x_5 = x_1 + 1
1251      12   goto L0;
1252      13 endif
1253 @end smallexample
1254
1255 We want to replace all the uses of @code{x_1} with the new definitions
1256 of @code{x_10} and @code{x_11}.  Note that the only uses that should
1257 be replaced are those at lines @code{5}, @code{9} and @code{11}.
1258 Also, the use of @code{x_7} at line @code{9} should @emph{not} be
1259 replaced (this is why we cannot just mark symbol @code{x} for
1260 renaming)@.
1261
1262 Additionally, we may need to insert a PHI node at line @code{11}
1263 because that is a merge point for @code{x_10} and @code{x_11}.  So the
1264 use of @code{x_1} at line @code{11} will be replaced with the new PHI
1265 node.  The insertion of PHI nodes is optional.  They are not strictly
1266 necessary to preserve the SSA form, and depending on what the caller
1267 inserted, they may not even be useful for the optimizers@.
1268
1269 Updating the SSA form is a two step process.  First, the pass has to
1270 identify which names need to be updated and/or which symbols need to
1271 be renamed into SSA form for the first time.  When new names are
1272 introduced to replace existing names in the program, the mapping
1273 between the old and the new names are registered by calling
1274 @code{register_new_name_mapping} (note that if your pass creates new
1275 code by duplicating basic blocks, the call to @code{tree_duplicate_bb}
1276 will set up the necessary mappings automatically).  On the other hand,
1277 if your pass exposes a new symbol that should be put in SSA form for
1278 the first time, the new symbol should be registered with
1279 @code{mark_sym_for_renaming}.
1280
1281 After the replacement mappings have been registered and new symbols
1282 marked for renaming, a call to @code{update_ssa} makes the registered
1283 changes.  This can be done with an explicit call or by creating
1284 @code{TODO} flags in the @code{tree_opt_pass} structure for your pass.
1285 There are several @code{TODO} flags that control the behavior of
1286 @code{update_ssa}:
1287
1288 @itemize @bullet
1289 @item @code{TODO_update_ssa}.  Update the SSA form inserting PHI nodes
1290       for newly exposed symbols and virtual names marked for updating.
1291       When updating real names, only insert PHI nodes for a real name
1292       @code{O_j} in blocks reached by all the new and old definitions for
1293       @code{O_j}.  If the iterated dominance frontier for @code{O_j}
1294       is not pruned, we may end up inserting PHI nodes in blocks that
1295       have one or more edges with no incoming definition for
1296       @code{O_j}.  This would lead to uninitialized warnings for
1297       @code{O_j}'s symbol@.
1298
1299 @item @code{TODO_update_ssa_no_phi}.  Update the SSA form without
1300       inserting any new PHI nodes at all.  This is used by passes that
1301       have either inserted all the PHI nodes themselves or passes that
1302       need only to patch use-def and def-def chains for virtuals
1303       (e.g., DCE)@.
1304
1305
1306 @item @code{TODO_update_ssa_full_phi}.  Insert PHI nodes everywhere
1307       they are needed.  No pruning of the IDF is done.  This is used
1308       by passes that need the PHI nodes for @code{O_j} even if it
1309       means that some arguments will come from the default definition
1310       of @code{O_j}'s symbol (e.g., @code{pass_linear_transform})@.
1311
1312       WARNING: If you need to use this flag, chances are that your
1313       pass may be doing something wrong.  Inserting PHI nodes for an
1314       old name where not all edges carry a new replacement may lead to
1315       silent codegen errors or spurious uninitialized warnings@.
1316
1317 @item @code{TODO_update_ssa_only_virtuals}.  Passes that update the
1318       SSA form on their own may want to delegate the updating of
1319       virtual names to the generic updater.  Since FUD chains are
1320       easier to maintain, this simplifies the work they need to do.
1321       NOTE: If this flag is used, any OLD->NEW mappings for real names
1322       are explicitly destroyed and only the symbols marked for
1323       renaming are processed@.
1324 @end itemize
1325
1326
1327 @subsection Examining @code{SSA_NAME} nodes
1328 @cindex examining SSA_NAMEs
1329
1330 The following macros can be used to examine @code{SSA_NAME} nodes
1331
1332 @defmac SSA_NAME_DEF_STMT (@var{var})
1333 Returns the statement @var{s} that creates the @code{SSA_NAME}
1334 @var{var}.  If @var{s} is an empty statement (i.e., @code{IS_EMPTY_STMT
1335 (@var{s})} returns @code{true}), it means that the first reference to
1336 this variable is a USE or a VUSE@.
1337 @end defmac
1338
1339 @defmac SSA_NAME_VERSION (@var{var})
1340 Returns the version number of the @code{SSA_NAME} object @var{var}.
1341 @end defmac
1342
1343
1344 @subsection Walking use-def chains
1345
1346 @deftypefn {Tree SSA function} void walk_use_def_chains (@var{var}, @var{fn}, @var{data})
1347
1348 Walks use-def chains starting at the @code{SSA_NAME} node @var{var}.
1349 Calls function @var{fn} at each reaching definition found.  Function
1350 @var{FN} takes three arguments: @var{var}, its defining statement
1351 (@var{def_stmt}) and a generic pointer to whatever state information
1352 that @var{fn} may want to maintain (@var{data}).  Function @var{fn} is
1353 able to stop the walk by returning @code{true}, otherwise in order to
1354 continue the walk, @var{fn} should return @code{false}.
1355
1356 Note, that if @var{def_stmt} is a @code{PHI} node, the semantics are
1357 slightly different.  For each argument @var{arg} of the PHI node, this
1358 function will:
1359
1360 @enumerate
1361 @item   Walk the use-def chains for @var{arg}.
1362 @item   Call @code{FN (@var{arg}, @var{phi}, @var{data})}.
1363 @end enumerate
1364
1365 Note how the first argument to @var{fn} is no longer the original
1366 variable @var{var}, but the PHI argument currently being examined.
1367 If @var{fn} wants to get at @var{var}, it should call
1368 @code{PHI_RESULT} (@var{phi}).
1369 @end deftypefn
1370
1371 @subsection Walking the dominator tree
1372
1373 @deftypefn {Tree SSA function} void walk_dominator_tree (@var{walk_data}, @var{bb})
1374
1375 This function walks the dominator tree for the current CFG calling a
1376 set of callback functions defined in @var{struct dom_walk_data} in
1377 @file{domwalk.h}.  The call back functions you need to define give you
1378 hooks to execute custom code at various points during traversal:
1379
1380 @enumerate
1381 @item Once to initialize any local data needed while processing
1382       @var{bb} and its children.  This local data is pushed into an
1383       internal stack which is automatically pushed and popped as the
1384       walker traverses the dominator tree.
1385
1386 @item Once before traversing all the statements in the @var{bb}.
1387
1388 @item Once for every statement inside @var{bb}.
1389
1390 @item Once after traversing all the statements and before recursing
1391       into @var{bb}'s dominator children.
1392
1393 @item It then recurses into all the dominator children of @var{bb}.
1394
1395 @item After recursing into all the dominator children of @var{bb} it
1396       can, optionally, traverse every statement in @var{bb} again
1397       (i.e., repeating steps 2 and 3).
1398
1399 @item Once after walking the statements in @var{bb} and @var{bb}'s
1400       dominator children.  At this stage, the block local data stack
1401       is popped.
1402 @end enumerate
1403 @end deftypefn
1404
1405 @node Alias analysis
1406 @section Alias analysis
1407 @cindex alias
1408 @cindex flow-sensitive alias analysis
1409 @cindex flow-insensitive alias analysis
1410
1411 Alias analysis proceeds in 4 main phases:
1412
1413 @enumerate
1414 @item   Structural alias analysis.
1415
1416 This phase walks the types for structure variables, and determines which
1417 of the fields can overlap using offset and size of each field.  For each
1418 field, a ``subvariable'' called a ``Structure field tag'' (SFT)@ is
1419 created, which represents that field as a separate variable.  All
1420 accesses that could possibly overlap with a given field will have
1421 virtual operands for the SFT of that field.
1422
1423 @smallexample
1424 struct foo
1425 @{
1426   int a;
1427   int b;
1428 @}
1429 struct foo temp;
1430 int bar (void)
1431 @{
1432   int tmp1, tmp2, tmp3;
1433   SFT.0_2 = V_MUST_DEF <SFT.0_1>
1434   temp.a = 5;
1435   SFT.1_4 = V_MUST_DEF <SFT.1_3>
1436   temp.b = 6;
1437   
1438   VUSE <SFT.1_4>
1439   tmp1_5 = temp.b;
1440   VUSE <SFT.0_2>
1441   tmp2_6 = temp.a;
1442
1443   tmp3_7 = tmp1_5 + tmp2_6;
1444   return tmp3_7;
1445 @}
1446 @end smallexample
1447
1448 If you copy the type tag for a variable for some reason, you probably
1449 also want to copy the subvariables for that variable.
1450
1451 @item   Points-to and escape analysis.
1452
1453 This phase walks the use-def chains in the SSA web looking for
1454 three things:
1455
1456         @itemize @bullet
1457         @item   Assignments of the form @code{P_i = &VAR}
1458         @item   Assignments of the form P_i = malloc()
1459         @item   Pointers and ADDR_EXPR that escape the current function.
1460         @end itemize
1461
1462 The concept of `escaping' is the same one used in the Java world.
1463 When a pointer or an ADDR_EXPR escapes, it means that it has been
1464 exposed outside of the current function.  So, assignment to
1465 global variables, function arguments and returning a pointer are
1466 all escape sites.
1467
1468 This is where we are currently limited.  Since not everything is
1469 renamed into SSA, we lose track of escape properties when a
1470 pointer is stashed inside a field in a structure, for instance.
1471 In those cases, we are assuming that the pointer does escape.
1472
1473 We use escape analysis to determine whether a variable is
1474 call-clobbered.  Simply put, if an ADDR_EXPR escapes, then the
1475 variable is call-clobbered.  If a pointer P_i escapes, then all
1476 the variables pointed-to by P_i (and its memory tag) also escape.
1477
1478 @item   Compute flow-sensitive aliases
1479
1480 We have two classes of memory tags.  Memory tags associated with
1481 the pointed-to data type of the pointers in the program.  These
1482 tags are called ``type memory tag'' (TMT)@.  The other class are
1483 those associated with SSA_NAMEs, called ``name memory tag'' (NMT)@.
1484 The basic idea is that when adding operands for an INDIRECT_REF
1485 *P_i, we will first check whether P_i has a name tag, if it does
1486 we use it, because that will have more precise aliasing
1487 information.  Otherwise, we use the standard type tag.
1488
1489 In this phase, we go through all the pointers we found in
1490 points-to analysis and create alias sets for the name memory tags
1491 associated with each pointer P_i.  If P_i escapes, we mark
1492 call-clobbered the variables it points to and its tag.
1493
1494
1495 @item   Compute flow-insensitive aliases
1496
1497 This pass will compare the alias set of every type memory tag and
1498 every addressable variable found in the program.  Given a type
1499 memory tag TMT and an addressable variable V@.  If the alias sets
1500 of TMT and V conflict (as computed by may_alias_p), then V is
1501 marked as an alias tag and added to the alias set of TMT@.
1502 @end enumerate
1503
1504 For instance, consider the following function:
1505
1506 @smallexample
1507 foo (int i)
1508 @{
1509   int *p, *q, a, b;
1510
1511   if (i > 10)
1512     p = &a;
1513   else
1514     q = &b;
1515
1516   *p = 3;
1517   *q = 5;
1518   a = b + 2;
1519   return *p;
1520 @}
1521 @end smallexample
1522
1523 After aliasing analysis has finished, the type memory tag for
1524 pointer @code{p} will have two aliases, namely variables @code{a} and
1525 @code{b}.
1526 Every time pointer @code{p} is dereferenced, we want to mark the
1527 operation as a potential reference to @code{a} and @code{b}.
1528
1529 @smallexample
1530 foo (int i)
1531 @{
1532   int *p, a, b;
1533
1534   if (i_2 > 10)
1535     p_4 = &a;
1536   else
1537     p_6 = &b;
1538   # p_1 = PHI <p_4(1), p_6(2)>;
1539
1540   # a_7 = V_MAY_DEF <a_3>;
1541   # b_8 = V_MAY_DEF <b_5>;
1542   *p_1 = 3;
1543
1544   # a_9 = V_MAY_DEF <a_7>
1545   # VUSE <b_8>
1546   a_9 = b_8 + 2;
1547
1548   # VUSE <a_9>;
1549   # VUSE <b_8>;
1550   return *p_1;
1551 @}
1552 @end smallexample
1553
1554 In certain cases, the list of may aliases for a pointer may grow
1555 too large.  This may cause an explosion in the number of virtual
1556 operands inserted in the code.  Resulting in increased memory
1557 consumption and compilation time.
1558
1559 When the number of virtual operands needed to represent aliased
1560 loads and stores grows too large (configurable with @option{--param
1561 max-aliased-vops}), alias sets are grouped to avoid severe
1562 compile-time slow downs and memory consumption.  The alias
1563 grouping heuristic proceeds as follows:
1564
1565 @enumerate
1566 @item Sort the list of pointers in decreasing number of contributed
1567 virtual operands.
1568
1569 @item Take the first pointer from the list and reverse the role
1570 of the memory tag and its aliases.  Usually, whenever an
1571 aliased variable Vi is found to alias with a memory tag
1572 T, we add Vi to the may-aliases set for T@.  Meaning that
1573 after alias analysis, we will have:
1574
1575 @smallexample
1576 may-aliases(T) = @{ V1, V2, V3, ..., Vn @}
1577 @end smallexample
1578
1579 This means that every statement that references T, will get
1580 @code{n} virtual operands for each of the Vi tags.  But, when
1581 alias grouping is enabled, we make T an alias tag and add it
1582 to the alias set of all the Vi variables:
1583
1584 @smallexample
1585 may-aliases(V1) = @{ T @}
1586 may-aliases(V2) = @{ T @}
1587 ...
1588 may-aliases(Vn) = @{ T @}
1589 @end smallexample
1590
1591 This has two effects: (a) statements referencing T will only get
1592 a single virtual operand, and, (b) all the variables Vi will now
1593 appear to alias each other.  So, we lose alias precision to
1594 improve compile time.  But, in theory, a program with such a high
1595 level of aliasing should not be very optimizable in the first
1596 place.
1597
1598 @item Since variables may be in the alias set of more than one
1599 memory tag, the grouping done in step (2) needs to be extended
1600 to all the memory tags that have a non-empty intersection with
1601 the may-aliases set of tag T@.  For instance, if we originally
1602 had these may-aliases sets:
1603
1604 @smallexample
1605 may-aliases(T) = @{ V1, V2, V3 @}
1606 may-aliases(R) = @{ V2, V4 @}
1607 @end smallexample
1608
1609 In step (2) we would have reverted the aliases for T as:
1610
1611 @smallexample
1612 may-aliases(V1) = @{ T @}
1613 may-aliases(V2) = @{ T @}
1614 may-aliases(V3) = @{ T @}
1615 @end smallexample
1616
1617 But note that now V2 is no longer aliased with R@.  We could
1618 add R to may-aliases(V2), but we are in the process of
1619 grouping aliases to reduce virtual operands so what we do is
1620 add V4 to the grouping to obtain:
1621
1622 @smallexample
1623 may-aliases(V1) = @{ T @}
1624 may-aliases(V2) = @{ T @}
1625 may-aliases(V3) = @{ T @}
1626 may-aliases(V4) = @{ T @}
1627 @end smallexample
1628
1629 @item If the total number of virtual operands due to aliasing is
1630 still above the threshold set by max-alias-vops, go back to (2).
1631 @end enumerate