OSDN Git Service

2005-06-15 Andrew Pinski <pinskia@physics.uc.edu>
[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                 | TARGET_MEM_REF
636                         op0 -> ID
637                         op1 -> val
638                         op2 -> val
639                         op3 -> CONST
640                         op4 -> CONST
641                 | REALPART_EXPR
642                         op0 -> inner-compref
643                 | IMAGPART_EXPR
644                         op0 -> inner-compref
645
646    inner-compref: min-lval
647                 | COMPONENT_REF
648                         op0 -> inner-compref
649                         op1 -> FIELD_DECL
650                         op2 -> val
651                 | ARRAY_REF
652                         op0 -> inner-compref
653                         op1 -> val
654                         op2 -> val
655                         op3 -> val
656                 | ARRAY_RANGE_REF
657                         op0 -> inner-compref
658                         op1 -> val
659                         op2 -> val
660                         op3 -> val
661                 | VIEW_CONVERT_EXPR
662                         op0 -> inner-compref
663
664    condition    : val
665                 | RELOP
666                         op0 -> val
667                         op1 -> val
668
669    val          : ID
670                 | CONST
671
672    rhs          : lhs
673                 | CONST
674                 | call-stmt
675                 | ADDR_EXPR
676                         op0 -> addr-expr-arg
677                 | UNOP
678                         op0 -> val
679                 | BINOP
680                         op0 -> val
681                         op1 -> val
682                 | RELOP
683                         op0 -> val
684                         op1 -> val
685 @end smallexample
686
687 @node Annotations
688 @section Annotations
689 @cindex annotations
690
691 The optimizers need to associate attributes with statements and
692 variables during the optimization process.  For instance, we need to
693 know what basic block a statement belongs to or whether a variable
694 has aliases.  All these attributes are stored in data structures
695 called annotations which are then linked to the field @code{ann} in
696 @code{struct tree_common}.
697
698 Presently, we define annotations for statements (@code{stmt_ann_t}),
699 variables (@code{var_ann_t}) and SSA names (@code{ssa_name_ann_t}).
700 Annotations are defined and documented in @file{tree-flow.h}.
701
702
703 @node Statement Operands
704 @section Statement Operands
705 @cindex operands
706 @cindex virtual operands
707 @cindex real operands
708 @findex update_stmt
709
710 Almost every GIMPLE statement will contain a reference to a variable
711 or memory location.  Since statements come in different shapes and
712 sizes, their operands are going to be located at various spots inside
713 the statement's tree.  To facilitate access to the statement's
714 operands, they are organized into lists associated inside each
715 statement's annotation.  Each element in an operand list is a pointer
716 to a @code{VAR_DECL}, @code{PARM_DECL} or @code{SSA_NAME} tree node.
717 This provides a very convenient way of examining and replacing
718 operands.
719
720 Data flow analysis and optimization is done on all tree nodes
721 representing variables.  Any node for which @code{SSA_VAR_P} returns
722 nonzero is considered when scanning statement operands.  However, not
723 all @code{SSA_VAR_P} variables are processed in the same way.  For the
724 purposes of optimization, we need to distinguish between references to
725 local scalar variables and references to globals, statics, structures,
726 arrays, aliased variables, etc.  The reason is simple, the compiler
727 can gather complete data flow information for a local scalar.  On the
728 other hand, a global variable may be modified by a function call, it
729 may not be possible to keep track of all the elements of an array or
730 the fields of a structure, etc.
731
732 The operand scanner gathers two kinds of operands: @dfn{real} and
733 @dfn{virtual}.  An operand for which @code{is_gimple_reg} returns true
734 is considered real, otherwise it is a virtual operand.  We also
735 distinguish between uses and definitions.  An operand is used if its
736 value is loaded by the statement (e.g., the operand at the RHS of an
737 assignment).  If the statement assigns a new value to the operand, the
738 operand is considered a definition (e.g., the operand at the LHS of
739 an assignment).
740
741 Virtual and real operands also have very different data flow
742 properties.  Real operands are unambiguous references to the
743 full object that they represent.  For instance, given
744
745 @smallexample
746 @{
747   int a, b;
748   a = b
749 @}
750 @end smallexample
751
752 Since @code{a} and @code{b} are non-aliased locals, the statement
753 @code{a = b} will have one real definition and one real use because
754 variable @code{b} is completely modified with the contents of
755 variable @code{a}.  Real definition are also known as @dfn{killing
756 definitions}.  Similarly, the use of @code{a} reads all its bits.
757
758 In contrast, virtual operands are used with variables that can have
759 a partial or ambiguous reference.  This includes structures, arrays,
760 globals, and aliased variables.  In these cases, we have two types of
761 definitions.  For globals, structures, and arrays, we can determine from
762 a statement whether a variable of these types has a killing definition.
763 If the variable does, then the statement is marked as having a
764 @dfn{must definition} of that variable.  However, if a statement is only
765 defining a part of the variable (i.e.@: a field in a structure), or if we
766 know that a statement might define the variable but we cannot say for sure,
767 then we mark that statement as having a @dfn{may definition}.  For
768 instance, given
769
770 @smallexample
771 @{
772   int a, b, *p;
773
774   if (...)
775     p = &a;
776   else
777     p = &b;
778   *p = 5;
779   return *p;
780 @}
781 @end smallexample
782
783 The assignment @code{*p = 5} may be a definition of @code{a} or
784 @code{b}.  If we cannot determine statically where @code{p} is
785 pointing to at the time of the store operation, we create virtual
786 definitions to mark that statement as a potential definition site for
787 @code{a} and @code{b}.  Memory loads are similarly marked with virtual
788 use operands.  Virtual operands are shown in tree dumps right before
789 the statement that contains them.  To request a tree dump with virtual
790 operands, use the @option{-vops} option to @option{-fdump-tree}:
791
792 @smallexample
793 @{
794   int a, b, *p;
795
796   if (...)
797     p = &a;
798   else
799     p = &b;
800   # a = V_MAY_DEF <a>
801   # b = V_MAY_DEF <b>
802   *p = 5;
803
804   # VUSE <a>
805   # VUSE <b>
806   return *p;
807 @}
808 @end smallexample
809
810 Notice that @code{V_MAY_DEF} operands have two copies of the referenced
811 variable.  This indicates that this is not a killing definition of
812 that variable.  In this case we refer to it as a @dfn{may definition}
813 or @dfn{aliased store}.  The presence of the second copy of the
814 variable in the @code{V_MAY_DEF} operand will become important when the
815 function is converted into SSA form.  This will be used to link all
816 the non-killing definitions to prevent optimizations from making
817 incorrect assumptions about them.
818
819 Operands are updated as soon as the statement is finished via a call
820 to @code{update_stmt}.  If statement elements are changed via
821 @code{SET_USE} or @code{SET_DEF}, then no further action is required
822 (ie, those macros take care of updating the statement).  If changes
823 are made by manipulating the statement's tree directly, then a call
824 must be made to @code{update_stmt} when complete.  Calling one of the
825 @code{bsi_insert} routines or @code{bsi_replace} performs an implicit
826 call to @code{update_stmt}.
827
828 @subsection Operand Iterators And Access Routines
829 @cindex Operand Iterators 
830 @cindex Operand Access Routines
831
832 Operands are collected by @file{tree-ssa-operands.c}.  They are stored
833 inside each statement's annotation and can be accessed through either the
834 operand iterators or an access routine.
835
836 The following access routines are available for examining operands:
837
838 @enumerate
839 @item @code{SINGLE_SSA_@{USE,DEF,TREE@}_OPERAND}: These accessors will return 
840 NULL unless there is exactly one operand matching the specified flags.  If 
841 there is exactly one operand, the operand is returned as either a @code{tree}, 
842 @code{def_operand_p}, or @code{use_operand_p}.
843
844 @smallexample
845 tree t = SINGLE_SSA_TREE_OPERAND (stmt, flags);
846 use_operand_p u = SINGLE_SSA_USE_OPERAND (stmt, SSA_ALL_VIRTUAL_USES);
847 def_operand_p d = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_ALL_DEFS);
848 @end smallexample
849
850 @item @code{ZERO_SSA_OPERANDS}: This macro returns true if there are no 
851 operands matching the specified flags.
852
853 @smallexample
854 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
855   return;
856 @end smallexample
857
858 @item @code{NUM_SSA_OPERANDS}: This macro Returns the number of operands 
859 matching 'flags'.  This actually executes a loop to perform the count, so 
860 only use this if it is really needed.
861
862 @smallexample
863 int count = NUM_SSA_OPERANDS (stmt, flags)
864 @end smallexample
865 @end enumerate
866
867
868 If you wish to iterate over some or all operands, use the
869 @code{FOR_EACH_SSA_@{USE,DEF,TREE@}_OPERAND} iterator.  For example, to print
870 all the operands for a statement:
871
872 @smallexample
873 void
874 print_ops (tree stmt)
875 @{
876   ssa_op_iter;
877   tree var;
878
879   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_OPERANDS)
880     print_generic_expr (stderr, var, TDF_SLIM);
881 @}
882 @end smallexample
883
884
885 How to choose the appropriate iterator:
886
887 @enumerate
888 @item Determine whether you are need to see the operand pointers, or just the
889     trees, and choose the appropriate macro:
890
891 @smallexample
892 Need            Macro:
893 ----            -------
894 use_operand_p   FOR_EACH_SSA_USE_OPERAND
895 def_operand_p   FOR_EACH_SSA_DEF_OPERAND
896 tree            FOR_EACH_SSA_TREE_OPERAND
897 @end smallexample
898
899 @item You need to declare a variable of the type you are interested
900     in, and an ssa_op_iter structure which serves as the loop
901     controlling variable.
902
903 @item Determine which operands you wish to use, and specify the flags of
904     those you are interested in.  They are documented in
905     @file{tree-ssa-operands.h}:
906
907 @smallexample
908 #define SSA_OP_USE              0x01    /* @r{Real USE operands.}  */
909 #define SSA_OP_DEF              0x02    /* @r{Real DEF operands.}  */
910 #define SSA_OP_VUSE             0x04    /* @r{VUSE operands.}  */
911 #define SSA_OP_VMAYUSE          0x08    /* @r{USE portion of V_MAY_DEFS.}  */
912 #define SSA_OP_VMAYDEF          0x10    /* @r{DEF portion of V_MAY_DEFS.}  */
913 #define SSA_OP_VMUSTDEF         0x20    /* @r{V_MUST_DEF definitions.}  */
914
915 /* @r{These are commonly grouped operand flags.}  */
916 #define SSA_OP_VIRTUAL_USES     (SSA_OP_VUSE | SSA_OP_VMAYUSE)
917 #define SSA_OP_VIRTUAL_DEFS     (SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF)
918 #define SSA_OP_ALL_USES         (SSA_OP_VIRTUAL_USES | SSA_OP_USE)
919 #define SSA_OP_ALL_DEFS         (SSA_OP_VIRTUAL_DEFS | SSA_OP_DEF)
920 #define SSA_OP_ALL_OPERANDS     (SSA_OP_ALL_USES | SSA_OP_ALL_DEFS)
921 @end smallexample
922 @end enumerate
923
924 So if you want to look at the use pointers for all the @code{USE} and
925 @code{VUSE} operands, you would do something like:
926
927 @smallexample
928   use_operand_p use_p;
929   ssa_op_iter iter;
930
931   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, (SSA_OP_USE | SSA_OP_VUSE))
932     @{
933       process_use_ptr (use_p);
934     @}
935 @end smallexample
936
937 The @code{TREE} macro is basically the same as the @code{USE} and
938 @code{DEF} macros, only with the use or def dereferenced via
939 @code{USE_FROM_PTR (use_p)} and @code{DEF_FROM_PTR (def_p)}.  Since we
940 aren't using operand pointers, use and defs flags can be mixed.
941
942 @smallexample
943   tree var;
944   ssa_op_iter iter;
945
946   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_VUSE | SSA_OP_VMUSTDEF)
947     @{
948        print_generic_expr (stderr, var, TDF_SLIM);
949     @}
950 @end smallexample
951
952 @code{V_MAY_DEF}s are broken into two flags, one for the
953 @code{DEF} portion (@code{SSA_OP_VMAYDEF}) and one for the USE portion
954 (@code{SSA_OP_VMAYUSE}).  If all you want to look at are the
955 @code{V_MAY_DEF}s together, there is a fourth iterator macro for this,
956 which returns both a def_operand_p and a use_operand_p for each
957 @code{V_MAY_DEF} in the statement.  Note that you don't need any flags for
958 this one.
959
960 @smallexample
961   use_operand_p use_p;
962   def_operand_p def_p;
963   ssa_op_iter iter;
964
965   FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
966     @{
967       my_code;
968     @}
969 @end smallexample
970
971 @code{V_MUST_DEF}s are broken into two flags, one for the
972 @code{DEF} portion (@code{SSA_OP_VMUSTDEF}) and one for the kill portion
973 (@code{SSA_OP_VMUSTKILL}).  If all you want to look at are the
974 @code{V_MUST_DEF}s together, there is a fourth iterator macro for this,
975 which returns both a def_operand_p and a use_operand_p for each
976 @code{V_MUST_DEF} in the statement.  Note that you don't need any flags for
977 this one.
978
979 @smallexample
980   use_operand_p kill_p;
981   def_operand_p def_p;
982   ssa_op_iter iter;
983
984   FOR_EACH_SSA_MUSTDEF_OPERAND (def_p, kill_p, stmt, iter)
985     @{
986       my_code;
987     @}
988 @end smallexample
989
990
991 There are many examples in the code as well, as well as the
992 documentation in @file{tree-ssa-operands.h}.
993
994 There are also a couple of variants on the stmt iterators regarding PHI
995 nodes.
996
997 @code{FOR_EACH_PHI_ARG} Works exactly like 
998 @code{FOR_EACH_SSA_USE_OPERAND}, except it works over @code{PHI} arguments 
999 instead of statement operands.
1000
1001 @smallexample
1002 /* Look at every virtual PHI use.  */
1003 FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_VIRTUAL_USES)
1004 @{
1005    my_code;
1006 @}
1007
1008 /* Look at every real PHI use.  */
1009 FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_USES)
1010   my_code;
1011
1012 /* Look at every every PHI use.  */
1013 FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_ALL_USES)
1014   my_code;
1015 @end smallexample
1016
1017 @code{FOR_EACH_PHI_OR_STMT_@{USE,DEF@}} works exactly like 
1018 @code{FOR_EACH_SSA_@{USE,DEF@}_OPERAND}, except it will function on
1019 either a statement or a @code{PHI} node.  These should be used when it is
1020 appropriate but they are not quite as efficient as the individual 
1021 @code{FOR_EACH_PHI} and @code{FOR_EACH_SSA} routines.
1022
1023 @smallexample
1024 FOR_EACH_PHI_OR_STMT_USE (use_operand_p, stmt, iter, flags)
1025   @{
1026      my_code;
1027   @}
1028
1029 FOR_EACH_PHI_OR_STMT_DEF (def_operand_p, phi, iter, flags)
1030   @{
1031      my_code;
1032   @}
1033 @end smallexample
1034
1035 @subsection Immediate Uses
1036 @cindex Immediate Uses
1037
1038 Immediate use information is now always available.  Using the immediate use 
1039 iterators, you may examine every use of any @code{SSA_NAME}. For instance,
1040 to change each use of @code{ssa_var} to @code{ssa_var2}:
1041
1042 @smallexample
1043   use_operand_p imm_use_p;
1044   imm_use_iterator iterator;
1045   tree ssa_var
1046
1047   FOR_EACH_IMM_USE_SAFE (imm_use_p, iterator, ssa_var)
1048     SET_USE (imm_use_p, ssa_var_2);
1049 @end smallexample
1050
1051 There are 2 iterators which can be used. @code{FOR_EACH_IMM_USE_FAST} is used 
1052 when the immediate uses are not changed, ie. you are looking at the uses, but 
1053 not setting them.  
1054
1055 If they do get changed, then care must be taken that things are not changed 
1056 under the iterators, so use the @code{FOR_EACH_IMM_USE_SAFE} iterator.  It 
1057 attempts to preserve the sanity of the use list by moving an iterator element
1058 through the use list, preventing insertions and deletions in the list from
1059 resulting in invalid pointers.  This is a little slower since it adds a
1060 placeholder element and moves it through the list.  This element must be 
1061 also be removed if the loop is terminated early.  A macro 
1062 (@code{BREAK_FROM SAFE_IMM_USE}) is provided for this:
1063
1064 @smallexample
1065   FOR_EACH_IMM_USE_SAFE (use_p, iter, var)
1066     @{
1067       if (var == last_var)
1068         BREAK_FROM_SAFE_IMM_USE (iter);
1069       else
1070         SET_USE (use_p, var2);
1071     @}
1072 @end smallexample
1073
1074 There are checks in @code{verify_ssa} which verify that the immediate use list
1075 is up to date, as well as checking that an optimization didn't break from the 
1076 loop without using this macro.  It is safe to simply 'break'; from a 
1077 @code{FOR_EACH_IMM_USE_FAST} traverse.
1078
1079 Some useful functions and macros:
1080 @enumerate
1081 @item  @code{has_zero_uses (ssa_var)} : Returns true if there are no uses of
1082 @code{ssa_var}.
1083 @item   @code{has_single_use (ssa_var)} : Returns true if there is only a 
1084 single use of @code{ssa_var}.
1085 @item   @code{single_imm_use (ssa_var, use_operand_p *ptr, tree *stmt)} :
1086 Returns true if there is only a single use of @code{ssa_var}, and also returns
1087 the use pointer and statement it occurs in in the second and third parameters.
1088 @item   @code{num_imm_uses (ssa_var)} : Returns the number of immediate uses of
1089 @code{ssa_var}. It is better not to use this if possible since it simply
1090 utilizes a loop to count the uses.
1091 @item  @code{PHI_ARG_INDEX_FROM_USE (use_p)} : Given a use within a @code{PHI}
1092 node, return the index number for the use.  An assert is triggered if the use
1093 isn't located in a @code{PHI} node.
1094 @item  @code{USE_STMT (use_p)} : Return the statement a use occurs in.
1095 @end enumerate
1096
1097 Note that uses are not put into an immediate use list until their statement is
1098 actually inserted into the instruction stream via a @code{bsi_*} routine.  
1099
1100 It is also still possible to utilize lazy updating of statements, but this 
1101 should be used only when absolutely required.  Both alias analysis and the 
1102 dominator optimizations currently do this.  
1103
1104 When lazy updating is being used, the immediate use information is out of date 
1105 and cannot be used reliably.  Lazy updating is achieved by simply marking
1106 statements modified via calls to @code{mark_stmt_modified} instead of 
1107 @code{update_stmt}.  When lazy updating is no longer required, all the 
1108 modified statements must have @code{update_stmt} called in order to bring them 
1109 up to date.  This must be done before the optimization is finished, or 
1110 @code{verify_ssa} will trigger an abort.
1111
1112 This is done with a simple loop over the instruction stream:
1113 @smallexample
1114   block_stmt_iterator bsi;
1115   basic_block bb;
1116   FOR_EACH_BB (bb)
1117     @{
1118       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1119         update_stmt_if_modified (bsi_stmt (bsi));
1120     @}
1121 @end smallexample
1122
1123 @node SSA
1124 @section Static Single Assignment
1125 @cindex SSA
1126 @cindex static single assignment
1127
1128 Most of the tree optimizers rely on the data flow information provided
1129 by the Static Single Assignment (SSA) form.  We implement the SSA form
1130 as described in @cite{R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and
1131 K. Zadeck.  Efficiently Computing Static Single Assignment Form and the
1132 Control Dependence Graph.  ACM Transactions on Programming Languages
1133 and Systems, 13(4):451-490, October 1991}.
1134
1135 The SSA form is based on the premise that program variables are
1136 assigned in exactly one location in the program.  Multiple assignments
1137 to the same variable create new versions of that variable.  Naturally,
1138 actual programs are seldom in SSA form initially because variables
1139 tend to be assigned multiple times.  The compiler modifies the program
1140 representation so that every time a variable is assigned in the code,
1141 a new version of the variable is created.  Different versions of the
1142 same variable are distinguished by subscripting the variable name with
1143 its version number.  Variables used in the right-hand side of
1144 expressions are renamed so that their version number matches that of
1145 the most recent assignment.
1146
1147 We represent variable versions using @code{SSA_NAME} nodes.  The
1148 renaming process in @file{tree-ssa.c} wraps every real and
1149 virtual operand with an @code{SSA_NAME} node which contains
1150 the version number and the statement that created the
1151 @code{SSA_NAME}.  Only definitions and virtual definitions may
1152 create new @code{SSA_NAME} nodes.
1153
1154 Sometimes, flow of control makes it impossible to determine what is the
1155 most recent version of a variable.  In these cases, the compiler
1156 inserts an artificial definition for that variable called
1157 @dfn{PHI function} or @dfn{PHI node}.  This new definition merges
1158 all the incoming versions of the variable to create a new name
1159 for it.  For instance,
1160
1161 @smallexample
1162 if (...)
1163   a_1 = 5;
1164 else if (...)
1165   a_2 = 2;
1166 else
1167   a_3 = 13;
1168
1169 # a_4 = PHI <a_1, a_2, a_3>
1170 return a_4;
1171 @end smallexample
1172
1173 Since it is not possible to determine which of the three branches
1174 will be taken at runtime, we don't know which of @code{a_1},
1175 @code{a_2} or @code{a_3} to use at the return statement.  So, the
1176 SSA renamer creates a new version @code{a_4} which is assigned
1177 the result of ``merging'' @code{a_1}, @code{a_2} and @code{a_3}.
1178 Hence, PHI nodes mean ``one of these operands.  I don't know
1179 which''.
1180
1181 The following macros can be used to examine PHI nodes
1182
1183 @defmac PHI_RESULT (@var{phi})
1184 Returns the @code{SSA_NAME} created by PHI node @var{phi} (i.e.,
1185 @var{phi}'s LHS)@.
1186 @end defmac
1187
1188 @defmac PHI_NUM_ARGS (@var{phi})
1189 Returns the number of arguments in @var{phi}.  This number is exactly
1190 the number of incoming edges to the basic block holding @var{phi}@.
1191 @end defmac
1192
1193 @defmac PHI_ARG_ELT (@var{phi}, @var{i})
1194 Returns a tuple representing the @var{i}th argument of @var{phi}@.
1195 Each element of this tuple contains an @code{SSA_NAME} @var{var} and
1196 the incoming edge through which @var{var} flows.
1197 @end defmac
1198
1199 @defmac PHI_ARG_EDGE (@var{phi}, @var{i})
1200 Returns the incoming edge for the @var{i}th argument of @var{phi}.
1201 @end defmac
1202
1203 @defmac PHI_ARG_DEF (@var{phi}, @var{i})
1204 Returns the @code{SSA_NAME} for the @var{i}th argument of @var{phi}.
1205 @end defmac
1206
1207
1208 @subsection Preserving the SSA form
1209 @findex update_ssa
1210 @cindex preserving SSA form
1211 Some optimization passes make changes to the function that
1212 invalidate the SSA property.  This can happen when a pass has
1213 added new symbols or changed the program so that variables that
1214 were previously aliased aren't anymore.  Whenever something like this
1215 happens, the affected symbols must be renamed into SSA form again.  
1216 Transformations that emit new code or replicate existing statements
1217 will also need to update the SSA form@.
1218
1219 Since GCC implements two different SSA forms for register and virtual
1220 variables, keeping the SSA form up to date depends on whether you are
1221 updating register or virtual names.  In both cases, the general idea
1222 behind incremental SSA updates is similar: when new SSA names are
1223 created, they typically are meant to replace other existing names in
1224 the program@.
1225
1226 For instance, given the following code:
1227
1228 @smallexample
1229      1  L0:
1230      2  x_1 = PHI (0, x_5)
1231      3  if (x_1 < 10)
1232      4    if (x_1 > 7)
1233      5      y_2 = 0
1234      6    else
1235      7      y_3 = x_1 + x_7
1236      8    endif
1237      9    x_5 = x_1 + 1
1238      10   goto L0;
1239      11 endif
1240 @end smallexample
1241
1242 Suppose that we insert new names @code{x_10} and @code{x_11} (lines
1243 @code{4} and @code{8})@.
1244
1245 @smallexample
1246      1  L0:
1247      2  x_1 = PHI (0, x_5)
1248      3  if (x_1 < 10)
1249      4    x_10 = ...
1250      5    if (x_1 > 7)
1251      6      y_2 = 0
1252      7    else
1253      8      x_11 = ...
1254      9      y_3 = x_1 + x_7
1255      10   endif
1256      11   x_5 = x_1 + 1
1257      12   goto L0;
1258      13 endif
1259 @end smallexample
1260
1261 We want to replace all the uses of @code{x_1} with the new definitions
1262 of @code{x_10} and @code{x_11}.  Note that the only uses that should
1263 be replaced are those at lines @code{5}, @code{9} and @code{11}.
1264 Also, the use of @code{x_7} at line @code{9} should @emph{not} be
1265 replaced (this is why we cannot just mark symbol @code{x} for
1266 renaming)@.
1267
1268 Additionally, we may need to insert a PHI node at line @code{11}
1269 because that is a merge point for @code{x_10} and @code{x_11}.  So the
1270 use of @code{x_1} at line @code{11} will be replaced with the new PHI
1271 node.  The insertion of PHI nodes is optional.  They are not strictly
1272 necessary to preserve the SSA form, and depending on what the caller
1273 inserted, they may not even be useful for the optimizers@.
1274
1275 Updating the SSA form is a two step process.  First, the pass has to
1276 identify which names need to be updated and/or which symbols need to
1277 be renamed into SSA form for the first time.  When new names are
1278 introduced to replace existing names in the program, the mapping
1279 between the old and the new names are registered by calling
1280 @code{register_new_name_mapping} (note that if your pass creates new
1281 code by duplicating basic blocks, the call to @code{tree_duplicate_bb}
1282 will set up the necessary mappings automatically).  On the other hand,
1283 if your pass exposes a new symbol that should be put in SSA form for
1284 the first time, the new symbol should be registered with
1285 @code{mark_sym_for_renaming}.
1286
1287 After the replacement mappings have been registered and new symbols
1288 marked for renaming, a call to @code{update_ssa} makes the registered
1289 changes.  This can be done with an explicit call or by creating
1290 @code{TODO} flags in the @code{tree_opt_pass} structure for your pass.
1291 There are several @code{TODO} flags that control the behavior of
1292 @code{update_ssa}:
1293
1294 @itemize @bullet
1295 @item @code{TODO_update_ssa}.  Update the SSA form inserting PHI nodes
1296       for newly exposed symbols and virtual names marked for updating.
1297       When updating real names, only insert PHI nodes for a real name
1298       @code{O_j} in blocks reached by all the new and old definitions for
1299       @code{O_j}.  If the iterated dominance frontier for @code{O_j}
1300       is not pruned, we may end up inserting PHI nodes in blocks that
1301       have one or more edges with no incoming definition for
1302       @code{O_j}.  This would lead to uninitialized warnings for
1303       @code{O_j}'s symbol@.
1304
1305 @item @code{TODO_update_ssa_no_phi}.  Update the SSA form without
1306       inserting any new PHI nodes at all.  This is used by passes that
1307       have either inserted all the PHI nodes themselves or passes that
1308       need only to patch use-def and def-def chains for virtuals
1309       (e.g., DCE)@.
1310
1311
1312 @item @code{TODO_update_ssa_full_phi}.  Insert PHI nodes everywhere
1313       they are needed.  No pruning of the IDF is done.  This is used
1314       by passes that need the PHI nodes for @code{O_j} even if it
1315       means that some arguments will come from the default definition
1316       of @code{O_j}'s symbol (e.g., @code{pass_linear_transform})@.
1317
1318       WARNING: If you need to use this flag, chances are that your
1319       pass may be doing something wrong.  Inserting PHI nodes for an
1320       old name where not all edges carry a new replacement may lead to
1321       silent codegen errors or spurious uninitialized warnings@.
1322
1323 @item @code{TODO_update_ssa_only_virtuals}.  Passes that update the
1324       SSA form on their own may want to delegate the updating of
1325       virtual names to the generic updater.  Since FUD chains are
1326       easier to maintain, this simplifies the work they need to do.
1327       NOTE: If this flag is used, any OLD->NEW mappings for real names
1328       are explicitly destroyed and only the symbols marked for
1329       renaming are processed@.
1330 @end itemize
1331
1332
1333 @subsection Examining @code{SSA_NAME} nodes
1334 @cindex examining SSA_NAMEs
1335
1336 The following macros can be used to examine @code{SSA_NAME} nodes
1337
1338 @defmac SSA_NAME_DEF_STMT (@var{var})
1339 Returns the statement @var{s} that creates the @code{SSA_NAME}
1340 @var{var}.  If @var{s} is an empty statement (i.e., @code{IS_EMPTY_STMT
1341 (@var{s})} returns @code{true}), it means that the first reference to
1342 this variable is a USE or a VUSE@.
1343 @end defmac
1344
1345 @defmac SSA_NAME_VERSION (@var{var})
1346 Returns the version number of the @code{SSA_NAME} object @var{var}.
1347 @end defmac
1348
1349
1350 @subsection Walking use-def chains
1351
1352 @deftypefn {Tree SSA function} void walk_use_def_chains (@var{var}, @var{fn}, @var{data})
1353
1354 Walks use-def chains starting at the @code{SSA_NAME} node @var{var}.
1355 Calls function @var{fn} at each reaching definition found.  Function
1356 @var{FN} takes three arguments: @var{var}, its defining statement
1357 (@var{def_stmt}) and a generic pointer to whatever state information
1358 that @var{fn} may want to maintain (@var{data}).  Function @var{fn} is
1359 able to stop the walk by returning @code{true}, otherwise in order to
1360 continue the walk, @var{fn} should return @code{false}.
1361
1362 Note, that if @var{def_stmt} is a @code{PHI} node, the semantics are
1363 slightly different.  For each argument @var{arg} of the PHI node, this
1364 function will:
1365
1366 @enumerate
1367 @item   Walk the use-def chains for @var{arg}.
1368 @item   Call @code{FN (@var{arg}, @var{phi}, @var{data})}.
1369 @end enumerate
1370
1371 Note how the first argument to @var{fn} is no longer the original
1372 variable @var{var}, but the PHI argument currently being examined.
1373 If @var{fn} wants to get at @var{var}, it should call
1374 @code{PHI_RESULT} (@var{phi}).
1375 @end deftypefn
1376
1377 @subsection Walking the dominator tree
1378
1379 @deftypefn {Tree SSA function} void walk_dominator_tree (@var{walk_data}, @var{bb})
1380
1381 This function walks the dominator tree for the current CFG calling a
1382 set of callback functions defined in @var{struct dom_walk_data} in
1383 @file{domwalk.h}.  The call back functions you need to define give you
1384 hooks to execute custom code at various points during traversal:
1385
1386 @enumerate
1387 @item Once to initialize any local data needed while processing
1388       @var{bb} and its children.  This local data is pushed into an
1389       internal stack which is automatically pushed and popped as the
1390       walker traverses the dominator tree.
1391
1392 @item Once before traversing all the statements in the @var{bb}.
1393
1394 @item Once for every statement inside @var{bb}.
1395
1396 @item Once after traversing all the statements and before recursing
1397       into @var{bb}'s dominator children.
1398
1399 @item It then recurses into all the dominator children of @var{bb}.
1400
1401 @item After recursing into all the dominator children of @var{bb} it
1402       can, optionally, traverse every statement in @var{bb} again
1403       (i.e., repeating steps 2 and 3).
1404
1405 @item Once after walking the statements in @var{bb} and @var{bb}'s
1406       dominator children.  At this stage, the block local data stack
1407       is popped.
1408 @end enumerate
1409 @end deftypefn
1410
1411 @node Alias analysis
1412 @section Alias analysis
1413 @cindex alias
1414 @cindex flow-sensitive alias analysis
1415 @cindex flow-insensitive alias analysis
1416
1417 Alias analysis proceeds in 4 main phases:
1418
1419 @enumerate
1420 @item   Structural alias analysis.
1421
1422 This phase walks the types for structure variables, and determines which
1423 of the fields can overlap using offset and size of each field.  For each
1424 field, a ``subvariable'' called a ``Structure field tag'' (SFT)@ is
1425 created, which represents that field as a separate variable.  All
1426 accesses that could possibly overlap with a given field will have
1427 virtual operands for the SFT of that field.
1428
1429 @smallexample
1430 struct foo
1431 @{
1432   int a;
1433   int b;
1434 @}
1435 struct foo temp;
1436 int bar (void)
1437 @{
1438   int tmp1, tmp2, tmp3;
1439   SFT.0_2 = V_MUST_DEF <SFT.0_1>
1440   temp.a = 5;
1441   SFT.1_4 = V_MUST_DEF <SFT.1_3>
1442   temp.b = 6;
1443   
1444   VUSE <SFT.1_4>
1445   tmp1_5 = temp.b;
1446   VUSE <SFT.0_2>
1447   tmp2_6 = temp.a;
1448
1449   tmp3_7 = tmp1_5 + tmp2_6;
1450   return tmp3_7;
1451 @}
1452 @end smallexample
1453
1454 If you copy the type tag for a variable for some reason, you probably
1455 also want to copy the subvariables for that variable.
1456
1457 @item   Points-to and escape analysis.
1458
1459 This phase walks the use-def chains in the SSA web looking for
1460 three things:
1461
1462         @itemize @bullet
1463         @item   Assignments of the form @code{P_i = &VAR}
1464         @item   Assignments of the form P_i = malloc()
1465         @item   Pointers and ADDR_EXPR that escape the current function.
1466         @end itemize
1467
1468 The concept of `escaping' is the same one used in the Java world.
1469 When a pointer or an ADDR_EXPR escapes, it means that it has been
1470 exposed outside of the current function.  So, assignment to
1471 global variables, function arguments and returning a pointer are
1472 all escape sites.
1473
1474 This is where we are currently limited.  Since not everything is
1475 renamed into SSA, we lose track of escape properties when a
1476 pointer is stashed inside a field in a structure, for instance.
1477 In those cases, we are assuming that the pointer does escape.
1478
1479 We use escape analysis to determine whether a variable is
1480 call-clobbered.  Simply put, if an ADDR_EXPR escapes, then the
1481 variable is call-clobbered.  If a pointer P_i escapes, then all
1482 the variables pointed-to by P_i (and its memory tag) also escape.
1483
1484 @item   Compute flow-sensitive aliases
1485
1486 We have two classes of memory tags.  Memory tags associated with
1487 the pointed-to data type of the pointers in the program.  These
1488 tags are called ``type memory tag'' (TMT)@.  The other class are
1489 those associated with SSA_NAMEs, called ``name memory tag'' (NMT)@.
1490 The basic idea is that when adding operands for an INDIRECT_REF
1491 *P_i, we will first check whether P_i has a name tag, if it does
1492 we use it, because that will have more precise aliasing
1493 information.  Otherwise, we use the standard type tag.
1494
1495 In this phase, we go through all the pointers we found in
1496 points-to analysis and create alias sets for the name memory tags
1497 associated with each pointer P_i.  If P_i escapes, we mark
1498 call-clobbered the variables it points to and its tag.
1499
1500
1501 @item   Compute flow-insensitive aliases
1502
1503 This pass will compare the alias set of every type memory tag and
1504 every addressable variable found in the program.  Given a type
1505 memory tag TMT and an addressable variable V@.  If the alias sets
1506 of TMT and V conflict (as computed by may_alias_p), then V is
1507 marked as an alias tag and added to the alias set of TMT@.
1508 @end enumerate
1509
1510 For instance, consider the following function:
1511
1512 @smallexample
1513 foo (int i)
1514 @{
1515   int *p, *q, a, b;
1516
1517   if (i > 10)
1518     p = &a;
1519   else
1520     q = &b;
1521
1522   *p = 3;
1523   *q = 5;
1524   a = b + 2;
1525   return *p;
1526 @}
1527 @end smallexample
1528
1529 After aliasing analysis has finished, the type memory tag for
1530 pointer @code{p} will have two aliases, namely variables @code{a} and
1531 @code{b}.
1532 Every time pointer @code{p} is dereferenced, we want to mark the
1533 operation as a potential reference to @code{a} and @code{b}.
1534
1535 @smallexample
1536 foo (int i)
1537 @{
1538   int *p, a, b;
1539
1540   if (i_2 > 10)
1541     p_4 = &a;
1542   else
1543     p_6 = &b;
1544   # p_1 = PHI <p_4(1), p_6(2)>;
1545
1546   # a_7 = V_MAY_DEF <a_3>;
1547   # b_8 = V_MAY_DEF <b_5>;
1548   *p_1 = 3;
1549
1550   # a_9 = V_MAY_DEF <a_7>
1551   # VUSE <b_8>
1552   a_9 = b_8 + 2;
1553
1554   # VUSE <a_9>;
1555   # VUSE <b_8>;
1556   return *p_1;
1557 @}
1558 @end smallexample
1559
1560 In certain cases, the list of may aliases for a pointer may grow
1561 too large.  This may cause an explosion in the number of virtual
1562 operands inserted in the code.  Resulting in increased memory
1563 consumption and compilation time.
1564
1565 When the number of virtual operands needed to represent aliased
1566 loads and stores grows too large (configurable with @option{--param
1567 max-aliased-vops}), alias sets are grouped to avoid severe
1568 compile-time slow downs and memory consumption.  The alias
1569 grouping heuristic proceeds as follows:
1570
1571 @enumerate
1572 @item Sort the list of pointers in decreasing number of contributed
1573 virtual operands.
1574
1575 @item Take the first pointer from the list and reverse the role
1576 of the memory tag and its aliases.  Usually, whenever an
1577 aliased variable Vi is found to alias with a memory tag
1578 T, we add Vi to the may-aliases set for T@.  Meaning that
1579 after alias analysis, we will have:
1580
1581 @smallexample
1582 may-aliases(T) = @{ V1, V2, V3, ..., Vn @}
1583 @end smallexample
1584
1585 This means that every statement that references T, will get
1586 @code{n} virtual operands for each of the Vi tags.  But, when
1587 alias grouping is enabled, we make T an alias tag and add it
1588 to the alias set of all the Vi variables:
1589
1590 @smallexample
1591 may-aliases(V1) = @{ T @}
1592 may-aliases(V2) = @{ T @}
1593 ...
1594 may-aliases(Vn) = @{ T @}
1595 @end smallexample
1596
1597 This has two effects: (a) statements referencing T will only get
1598 a single virtual operand, and, (b) all the variables Vi will now
1599 appear to alias each other.  So, we lose alias precision to
1600 improve compile time.  But, in theory, a program with such a high
1601 level of aliasing should not be very optimizable in the first
1602 place.
1603
1604 @item Since variables may be in the alias set of more than one
1605 memory tag, the grouping done in step (2) needs to be extended
1606 to all the memory tags that have a non-empty intersection with
1607 the may-aliases set of tag T@.  For instance, if we originally
1608 had these may-aliases sets:
1609
1610 @smallexample
1611 may-aliases(T) = @{ V1, V2, V3 @}
1612 may-aliases(R) = @{ V2, V4 @}
1613 @end smallexample
1614
1615 In step (2) we would have reverted the aliases for T as:
1616
1617 @smallexample
1618 may-aliases(V1) = @{ T @}
1619 may-aliases(V2) = @{ T @}
1620 may-aliases(V3) = @{ T @}
1621 @end smallexample
1622
1623 But note that now V2 is no longer aliased with R@.  We could
1624 add R to may-aliases(V2), but we are in the process of
1625 grouping aliases to reduce virtual operands so what we do is
1626 add V4 to the grouping to obtain:
1627
1628 @smallexample
1629 may-aliases(V1) = @{ T @}
1630 may-aliases(V2) = @{ T @}
1631 may-aliases(V3) = @{ T @}
1632 may-aliases(V4) = @{ T @}
1633 @end smallexample
1634
1635 @item If the total number of virtual operands due to aliasing is
1636 still above the threshold set by max-alias-vops, go back to (2).
1637 @end enumerate