1@c Copyright (C) 2004-2015 Free Software Foundation, Inc. 2@c This is part of the GCC manual. 3@c For copying conditions, see the file gcc.texi. 4 5@c --------------------------------------------------------------------- 6@c Tree SSA 7@c --------------------------------------------------------------------- 8 9@node Tree SSA 10@chapter Analysis and Optimization of GIMPLE tuples 11@cindex Tree SSA 12@cindex Optimization infrastructure for GIMPLE 13 14GCC uses three main intermediate languages to represent the program 15during compilation: GENERIC, GIMPLE and RTL@. GENERIC is a 16language-independent representation generated by each front end. It 17is used to serve as an interface between the parser and optimizer. 18GENERIC is a common representation that is able to represent programs 19written in all the languages supported by GCC@. 20 21GIMPLE and RTL are used to optimize the program. GIMPLE is used for 22target and language independent optimizations (e.g., inlining, 23constant propagation, tail call elimination, redundancy elimination, 24etc). Much like GENERIC, GIMPLE is a language independent, tree based 25representation. However, it differs from GENERIC in that the GIMPLE 26grammar is more restrictive: expressions contain no more than 3 27operands (except function calls), it has no control flow structures 28and expressions with side-effects are only allowed on the right hand 29side of assignments. See the chapter describing GENERIC and GIMPLE 30for more details. 31 32This chapter describes the data structures and functions used in the 33GIMPLE optimizers (also known as ``tree optimizers'' or ``middle 34end''). In particular, it focuses on all the macros, data structures, 35functions and programming constructs needed to implement optimization 36passes for GIMPLE@. 37 38@menu 39* Annotations:: Attributes for variables. 40* SSA Operands:: SSA names referenced by GIMPLE statements. 41* SSA:: Static Single Assignment representation. 42* Alias analysis:: Representing aliased loads and stores. 43* Memory model:: Memory model used by the middle-end. 44@end menu 45 46@node Annotations 47@section Annotations 48@cindex annotations 49 50The optimizers need to associate attributes with variables during the 51optimization process. For instance, we need to know whether a 52variable has aliases. All these attributes are stored in data 53structures called annotations which are then linked to the field 54@code{ann} in @code{struct tree_common}. 55 56 57@node SSA Operands 58@section SSA Operands 59@cindex operands 60@cindex virtual operands 61@cindex real operands 62@findex update_stmt 63 64Almost every GIMPLE statement will contain a reference to a variable 65or memory location. Since statements come in different shapes and 66sizes, their operands are going to be located at various spots inside 67the statement's tree. To facilitate access to the statement's 68operands, they are organized into lists associated inside each 69statement's annotation. Each element in an operand list is a pointer 70to a @code{VAR_DECL}, @code{PARM_DECL} or @code{SSA_NAME} tree node. 71This provides a very convenient way of examining and replacing 72operands. 73 74Data flow analysis and optimization is done on all tree nodes 75representing variables. Any node for which @code{SSA_VAR_P} returns 76nonzero is considered when scanning statement operands. However, not 77all @code{SSA_VAR_P} variables are processed in the same way. For the 78purposes of optimization, we need to distinguish between references to 79local scalar variables and references to globals, statics, structures, 80arrays, aliased variables, etc. The reason is simple, the compiler 81can gather complete data flow information for a local scalar. On the 82other hand, a global variable may be modified by a function call, it 83may not be possible to keep track of all the elements of an array or 84the fields of a structure, etc. 85 86The operand scanner gathers two kinds of operands: @dfn{real} and 87@dfn{virtual}. An operand for which @code{is_gimple_reg} returns true 88is considered real, otherwise it is a virtual operand. We also 89distinguish between uses and definitions. An operand is used if its 90value is loaded by the statement (e.g., the operand at the RHS of an 91assignment). If the statement assigns a new value to the operand, the 92operand is considered a definition (e.g., the operand at the LHS of 93an assignment). 94 95Virtual and real operands also have very different data flow 96properties. Real operands are unambiguous references to the 97full object that they represent. For instance, given 98 99@smallexample 100@{ 101 int a, b; 102 a = b 103@} 104@end smallexample 105 106Since @code{a} and @code{b} are non-aliased locals, the statement 107@code{a = b} will have one real definition and one real use because 108variable @code{a} is completely modified with the contents of 109variable @code{b}. Real definition are also known as @dfn{killing 110definitions}. Similarly, the use of @code{b} reads all its bits. 111 112In contrast, virtual operands are used with variables that can have 113a partial or ambiguous reference. This includes structures, arrays, 114globals, and aliased variables. In these cases, we have two types of 115definitions. For globals, structures, and arrays, we can determine from 116a statement whether a variable of these types has a killing definition. 117If the variable does, then the statement is marked as having a 118@dfn{must definition} of that variable. However, if a statement is only 119defining a part of the variable (i.e.@: a field in a structure), or if we 120know that a statement might define the variable but we cannot say for sure, 121then we mark that statement as having a @dfn{may definition}. For 122instance, given 123 124@smallexample 125@{ 126 int a, b, *p; 127 128 if (@dots{}) 129 p = &a; 130 else 131 p = &b; 132 *p = 5; 133 return *p; 134@} 135@end smallexample 136 137The assignment @code{*p = 5} may be a definition of @code{a} or 138@code{b}. If we cannot determine statically where @code{p} is 139pointing to at the time of the store operation, we create virtual 140definitions to mark that statement as a potential definition site for 141@code{a} and @code{b}. Memory loads are similarly marked with virtual 142use operands. Virtual operands are shown in tree dumps right before 143the statement that contains them. To request a tree dump with virtual 144operands, use the @option{-vops} option to @option{-fdump-tree}: 145 146@smallexample 147@{ 148 int a, b, *p; 149 150 if (@dots{}) 151 p = &a; 152 else 153 p = &b; 154 # a = VDEF <a> 155 # b = VDEF <b> 156 *p = 5; 157 158 # VUSE <a> 159 # VUSE <b> 160 return *p; 161@} 162@end smallexample 163 164Notice that @code{VDEF} operands have two copies of the referenced 165variable. This indicates that this is not a killing definition of 166that variable. In this case we refer to it as a @dfn{may definition} 167or @dfn{aliased store}. The presence of the second copy of the 168variable in the @code{VDEF} operand will become important when the 169function is converted into SSA form. This will be used to link all 170the non-killing definitions to prevent optimizations from making 171incorrect assumptions about them. 172 173Operands are updated as soon as the statement is finished via a call 174to @code{update_stmt}. If statement elements are changed via 175@code{SET_USE} or @code{SET_DEF}, then no further action is required 176(i.e., those macros take care of updating the statement). If changes 177are made by manipulating the statement's tree directly, then a call 178must be made to @code{update_stmt} when complete. Calling one of the 179@code{bsi_insert} routines or @code{bsi_replace} performs an implicit 180call to @code{update_stmt}. 181 182@subsection Operand Iterators And Access Routines 183@cindex Operand Iterators 184@cindex Operand Access Routines 185 186Operands are collected by @file{tree-ssa-operands.c}. They are stored 187inside each statement's annotation and can be accessed through either the 188operand iterators or an access routine. 189 190The following access routines are available for examining operands: 191 192@enumerate 193@item @code{SINGLE_SSA_@{USE,DEF,TREE@}_OPERAND}: These accessors will return 194NULL unless there is exactly one operand matching the specified flags. If 195there is exactly one operand, the operand is returned as either a @code{tree}, 196@code{def_operand_p}, or @code{use_operand_p}. 197 198@smallexample 199tree t = SINGLE_SSA_TREE_OPERAND (stmt, flags); 200use_operand_p u = SINGLE_SSA_USE_OPERAND (stmt, SSA_ALL_VIRTUAL_USES); 201def_operand_p d = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_ALL_DEFS); 202@end smallexample 203 204@item @code{ZERO_SSA_OPERANDS}: This macro returns true if there are no 205operands matching the specified flags. 206 207@smallexample 208if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) 209 return; 210@end smallexample 211 212@item @code{NUM_SSA_OPERANDS}: This macro Returns the number of operands 213matching 'flags'. This actually executes a loop to perform the count, so 214only use this if it is really needed. 215 216@smallexample 217int count = NUM_SSA_OPERANDS (stmt, flags) 218@end smallexample 219@end enumerate 220 221 222If you wish to iterate over some or all operands, use the 223@code{FOR_EACH_SSA_@{USE,DEF,TREE@}_OPERAND} iterator. For example, to print 224all the operands for a statement: 225 226@smallexample 227void 228print_ops (tree stmt) 229@{ 230 ssa_op_iter; 231 tree var; 232 233 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_OPERANDS) 234 print_generic_expr (stderr, var, TDF_SLIM); 235@} 236@end smallexample 237 238 239How to choose the appropriate iterator: 240 241@enumerate 242@item Determine whether you are need to see the operand pointers, or just the 243trees, and choose the appropriate macro: 244 245@smallexample 246Need Macro: 247---- ------- 248use_operand_p FOR_EACH_SSA_USE_OPERAND 249def_operand_p FOR_EACH_SSA_DEF_OPERAND 250tree FOR_EACH_SSA_TREE_OPERAND 251@end smallexample 252 253@item You need to declare a variable of the type you are interested 254in, and an ssa_op_iter structure which serves as the loop controlling 255variable. 256 257@item Determine which operands you wish to use, and specify the flags of 258those you are interested in. They are documented in 259@file{tree-ssa-operands.h}: 260 261@smallexample 262#define SSA_OP_USE 0x01 /* @r{Real USE operands.} */ 263#define SSA_OP_DEF 0x02 /* @r{Real DEF operands.} */ 264#define SSA_OP_VUSE 0x04 /* @r{VUSE operands.} */ 265#define SSA_OP_VDEF 0x08 /* @r{VDEF operands.} */ 266 267/* @r{These are commonly grouped operand flags.} */ 268#define SSA_OP_VIRTUAL_USES (SSA_OP_VUSE) 269#define SSA_OP_VIRTUAL_DEFS (SSA_OP_VDEF) 270#define SSA_OP_ALL_VIRTUALS (SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_DEFS) 271#define SSA_OP_ALL_USES (SSA_OP_VIRTUAL_USES | SSA_OP_USE) 272#define SSA_OP_ALL_DEFS (SSA_OP_VIRTUAL_DEFS | SSA_OP_DEF) 273#define SSA_OP_ALL_OPERANDS (SSA_OP_ALL_USES | SSA_OP_ALL_DEFS) 274@end smallexample 275@end enumerate 276 277So if you want to look at the use pointers for all the @code{USE} and 278@code{VUSE} operands, you would do something like: 279 280@smallexample 281 use_operand_p use_p; 282 ssa_op_iter iter; 283 284 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, (SSA_OP_USE | SSA_OP_VUSE)) 285 @{ 286 process_use_ptr (use_p); 287 @} 288@end smallexample 289 290The @code{TREE} macro is basically the same as the @code{USE} and 291@code{DEF} macros, only with the use or def dereferenced via 292@code{USE_FROM_PTR (use_p)} and @code{DEF_FROM_PTR (def_p)}. Since we 293aren't using operand pointers, use and defs flags can be mixed. 294 295@smallexample 296 tree var; 297 ssa_op_iter iter; 298 299 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_VUSE) 300 @{ 301 print_generic_expr (stderr, var, TDF_SLIM); 302 @} 303@end smallexample 304 305@code{VDEF}s are broken into two flags, one for the 306@code{DEF} portion (@code{SSA_OP_VDEF}) and one for the USE portion 307(@code{SSA_OP_VUSE}). 308 309There are many examples in the code, in addition to the documentation 310in @file{tree-ssa-operands.h} and @file{ssa-iterators.h}. 311 312There are also a couple of variants on the stmt iterators regarding PHI 313nodes. 314 315@code{FOR_EACH_PHI_ARG} Works exactly like 316@code{FOR_EACH_SSA_USE_OPERAND}, except it works over @code{PHI} arguments 317instead of statement operands. 318 319@smallexample 320/* Look at every virtual PHI use. */ 321FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_VIRTUAL_USES) 322@{ 323 my_code; 324@} 325 326/* Look at every real PHI use. */ 327FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_USES) 328 my_code; 329 330/* Look at every PHI use. */ 331FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_ALL_USES) 332 my_code; 333@end smallexample 334 335@code{FOR_EACH_PHI_OR_STMT_@{USE,DEF@}} works exactly like 336@code{FOR_EACH_SSA_@{USE,DEF@}_OPERAND}, except it will function on 337either a statement or a @code{PHI} node. These should be used when it is 338appropriate but they are not quite as efficient as the individual 339@code{FOR_EACH_PHI} and @code{FOR_EACH_SSA} routines. 340 341@smallexample 342FOR_EACH_PHI_OR_STMT_USE (use_operand_p, stmt, iter, flags) 343 @{ 344 my_code; 345 @} 346 347FOR_EACH_PHI_OR_STMT_DEF (def_operand_p, phi, iter, flags) 348 @{ 349 my_code; 350 @} 351@end smallexample 352 353@subsection Immediate Uses 354@cindex Immediate Uses 355 356Immediate use information is now always available. Using the immediate use 357iterators, you may examine every use of any @code{SSA_NAME}. For instance, 358to change each use of @code{ssa_var} to @code{ssa_var2} and call fold_stmt on 359each stmt after that is done: 360 361@smallexample 362 use_operand_p imm_use_p; 363 imm_use_iterator iterator; 364 tree ssa_var, stmt; 365 366 367 FOR_EACH_IMM_USE_STMT (stmt, iterator, ssa_var) 368 @{ 369 FOR_EACH_IMM_USE_ON_STMT (imm_use_p, iterator) 370 SET_USE (imm_use_p, ssa_var_2); 371 fold_stmt (stmt); 372 @} 373@end smallexample 374 375There are 2 iterators which can be used. @code{FOR_EACH_IMM_USE_FAST} is 376used when the immediate uses are not changed, i.e., you are looking at the 377uses, but not setting them. 378 379If they do get changed, then care must be taken that things are not changed 380under the iterators, so use the @code{FOR_EACH_IMM_USE_STMT} and 381@code{FOR_EACH_IMM_USE_ON_STMT} iterators. They attempt to preserve the 382sanity of the use list by moving all the uses for a statement into 383a controlled position, and then iterating over those uses. Then the 384optimization can manipulate the stmt when all the uses have been 385processed. This is a little slower than the FAST version since it adds a 386placeholder element and must sort through the list a bit for each statement. 387This placeholder element must be also be removed if the loop is 388terminated early. The macro @code{BREAK_FROM_IMM_USE_SAFE} is provided 389to do this : 390 391@smallexample 392 FOR_EACH_IMM_USE_STMT (stmt, iterator, ssa_var) 393 @{ 394 if (stmt == last_stmt) 395 BREAK_FROM_SAFE_IMM_USE (iter); 396 397 FOR_EACH_IMM_USE_ON_STMT (imm_use_p, iterator) 398 SET_USE (imm_use_p, ssa_var_2); 399 fold_stmt (stmt); 400 @} 401@end smallexample 402 403There are checks in @code{verify_ssa} which verify that the immediate use list 404is up to date, as well as checking that an optimization didn't break from the 405loop without using this macro. It is safe to simply 'break'; from a 406@code{FOR_EACH_IMM_USE_FAST} traverse. 407 408Some useful functions and macros: 409@enumerate 410@item @code{has_zero_uses (ssa_var)} : Returns true if there are no uses of 411@code{ssa_var}. 412@item @code{has_single_use (ssa_var)} : Returns true if there is only a 413single use of @code{ssa_var}. 414@item @code{single_imm_use (ssa_var, use_operand_p *ptr, tree *stmt)} : 415Returns true if there is only a single use of @code{ssa_var}, and also returns 416the use pointer and statement it occurs in, in the second and third parameters. 417@item @code{num_imm_uses (ssa_var)} : Returns the number of immediate uses of 418@code{ssa_var}. It is better not to use this if possible since it simply 419utilizes a loop to count the uses. 420@item @code{PHI_ARG_INDEX_FROM_USE (use_p)} : Given a use within a @code{PHI} 421node, return the index number for the use. An assert is triggered if the use 422isn't located in a @code{PHI} node. 423@item @code{USE_STMT (use_p)} : Return the statement a use occurs in. 424@end enumerate 425 426Note that uses are not put into an immediate use list until their statement is 427actually inserted into the instruction stream via a @code{bsi_*} routine. 428 429It is also still possible to utilize lazy updating of statements, but this 430should be used only when absolutely required. Both alias analysis and the 431dominator optimizations currently do this. 432 433When lazy updating is being used, the immediate use information is out of date 434and cannot be used reliably. Lazy updating is achieved by simply marking 435statements modified via calls to @code{mark_stmt_modified} instead of 436@code{update_stmt}. When lazy updating is no longer required, all the 437modified statements must have @code{update_stmt} called in order to bring them 438up to date. This must be done before the optimization is finished, or 439@code{verify_ssa} will trigger an abort. 440 441This is done with a simple loop over the instruction stream: 442@smallexample 443 block_stmt_iterator bsi; 444 basic_block bb; 445 FOR_EACH_BB (bb) 446 @{ 447 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 448 update_stmt_if_modified (bsi_stmt (bsi)); 449 @} 450@end smallexample 451 452@node SSA 453@section Static Single Assignment 454@cindex SSA 455@cindex static single assignment 456 457Most of the tree optimizers rely on the data flow information provided 458by the Static Single Assignment (SSA) form. We implement the SSA form 459as described in @cite{R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and 460K. Zadeck. Efficiently Computing Static Single Assignment Form and the 461Control Dependence Graph. ACM Transactions on Programming Languages 462and Systems, 13(4):451-490, October 1991}. 463 464The SSA form is based on the premise that program variables are 465assigned in exactly one location in the program. Multiple assignments 466to the same variable create new versions of that variable. Naturally, 467actual programs are seldom in SSA form initially because variables 468tend to be assigned multiple times. The compiler modifies the program 469representation so that every time a variable is assigned in the code, 470a new version of the variable is created. Different versions of the 471same variable are distinguished by subscripting the variable name with 472its version number. Variables used in the right-hand side of 473expressions are renamed so that their version number matches that of 474the most recent assignment. 475 476We represent variable versions using @code{SSA_NAME} nodes. The 477renaming process in @file{tree-ssa.c} wraps every real and 478virtual operand with an @code{SSA_NAME} node which contains 479the version number and the statement that created the 480@code{SSA_NAME}. Only definitions and virtual definitions may 481create new @code{SSA_NAME} nodes. 482 483@cindex PHI nodes 484Sometimes, flow of control makes it impossible to determine the 485most recent version of a variable. In these cases, the compiler 486inserts an artificial definition for that variable called 487@dfn{PHI function} or @dfn{PHI node}. This new definition merges 488all the incoming versions of the variable to create a new name 489for it. For instance, 490 491@smallexample 492if (@dots{}) 493 a_1 = 5; 494else if (@dots{}) 495 a_2 = 2; 496else 497 a_3 = 13; 498 499# a_4 = PHI <a_1, a_2, a_3> 500return a_4; 501@end smallexample 502 503Since it is not possible to determine which of the three branches 504will be taken at runtime, we don't know which of @code{a_1}, 505@code{a_2} or @code{a_3} to use at the return statement. So, the 506SSA renamer creates a new version @code{a_4} which is assigned 507the result of ``merging'' @code{a_1}, @code{a_2} and @code{a_3}. 508Hence, PHI nodes mean ``one of these operands. I don't know 509which''. 510 511The following functions can be used to examine PHI nodes 512 513@defun gimple_phi_result (@var{phi}) 514Returns the @code{SSA_NAME} created by PHI node @var{phi} (i.e., 515@var{phi}'s LHS)@. 516@end defun 517 518@defun gimple_phi_num_args (@var{phi}) 519Returns the number of arguments in @var{phi}. This number is exactly 520the number of incoming edges to the basic block holding @var{phi}@. 521@end defun 522 523@defun gimple_phi_arg (@var{phi}, @var{i}) 524Returns @var{i}th argument of @var{phi}@. 525@end defun 526 527@defun gimple_phi_arg_edge (@var{phi}, @var{i}) 528Returns the incoming edge for the @var{i}th argument of @var{phi}. 529@end defun 530 531@defun gimple_phi_arg_def (@var{phi}, @var{i}) 532Returns the @code{SSA_NAME} for the @var{i}th argument of @var{phi}. 533@end defun 534 535 536@subsection Preserving the SSA form 537@findex update_ssa 538@cindex preserving SSA form 539Some optimization passes make changes to the function that 540invalidate the SSA property. This can happen when a pass has 541added new symbols or changed the program so that variables that 542were previously aliased aren't anymore. Whenever something like this 543happens, the affected symbols must be renamed into SSA form again. 544Transformations that emit new code or replicate existing statements 545will also need to update the SSA form@. 546 547Since GCC implements two different SSA forms for register and virtual 548variables, keeping the SSA form up to date depends on whether you are 549updating register or virtual names. In both cases, the general idea 550behind incremental SSA updates is similar: when new SSA names are 551created, they typically are meant to replace other existing names in 552the program@. 553 554For instance, given the following code: 555 556@smallexample 557 1 L0: 558 2 x_1 = PHI (0, x_5) 559 3 if (x_1 < 10) 560 4 if (x_1 > 7) 561 5 y_2 = 0 562 6 else 563 7 y_3 = x_1 + x_7 564 8 endif 565 9 x_5 = x_1 + 1 566 10 goto L0; 567 11 endif 568@end smallexample 569 570Suppose that we insert new names @code{x_10} and @code{x_11} (lines 571@code{4} and @code{8})@. 572 573@smallexample 574 1 L0: 575 2 x_1 = PHI (0, x_5) 576 3 if (x_1 < 10) 577 4 x_10 = @dots{} 578 5 if (x_1 > 7) 579 6 y_2 = 0 580 7 else 581 8 x_11 = @dots{} 582 9 y_3 = x_1 + x_7 583 10 endif 584 11 x_5 = x_1 + 1 585 12 goto L0; 586 13 endif 587@end smallexample 588 589We want to replace all the uses of @code{x_1} with the new definitions 590of @code{x_10} and @code{x_11}. Note that the only uses that should 591be replaced are those at lines @code{5}, @code{9} and @code{11}. 592Also, the use of @code{x_7} at line @code{9} should @emph{not} be 593replaced (this is why we cannot just mark symbol @code{x} for 594renaming)@. 595 596Additionally, we may need to insert a PHI node at line @code{11} 597because that is a merge point for @code{x_10} and @code{x_11}. So the 598use of @code{x_1} at line @code{11} will be replaced with the new PHI 599node. The insertion of PHI nodes is optional. They are not strictly 600necessary to preserve the SSA form, and depending on what the caller 601inserted, they may not even be useful for the optimizers@. 602 603Updating the SSA form is a two step process. First, the pass has to 604identify which names need to be updated and/or which symbols need to 605be renamed into SSA form for the first time. When new names are 606introduced to replace existing names in the program, the mapping 607between the old and the new names are registered by calling 608@code{register_new_name_mapping} (note that if your pass creates new 609code by duplicating basic blocks, the call to @code{tree_duplicate_bb} 610will set up the necessary mappings automatically). 611 612After the replacement mappings have been registered and new symbols 613marked for renaming, a call to @code{update_ssa} makes the registered 614changes. This can be done with an explicit call or by creating 615@code{TODO} flags in the @code{tree_opt_pass} structure for your pass. 616There are several @code{TODO} flags that control the behavior of 617@code{update_ssa}: 618 619@itemize @bullet 620@item @code{TODO_update_ssa}. Update the SSA form inserting PHI nodes 621for newly exposed symbols and virtual names marked for updating. 622When updating real names, only insert PHI nodes for a real name 623@code{O_j} in blocks reached by all the new and old definitions for 624@code{O_j}. If the iterated dominance frontier for @code{O_j} 625is not pruned, we may end up inserting PHI nodes in blocks that 626have one or more edges with no incoming definition for 627@code{O_j}. This would lead to uninitialized warnings for 628@code{O_j}'s symbol@. 629 630@item @code{TODO_update_ssa_no_phi}. Update the SSA form without 631inserting any new PHI nodes at all. This is used by passes that 632have either inserted all the PHI nodes themselves or passes that 633need only to patch use-def and def-def chains for virtuals 634(e.g., DCE)@. 635 636 637@item @code{TODO_update_ssa_full_phi}. Insert PHI nodes everywhere 638they are needed. No pruning of the IDF is done. This is used 639by passes that need the PHI nodes for @code{O_j} even if it 640means that some arguments will come from the default definition 641of @code{O_j}'s symbol (e.g., @code{pass_linear_transform})@. 642 643WARNING: If you need to use this flag, chances are that your 644pass may be doing something wrong. Inserting PHI nodes for an 645old name where not all edges carry a new replacement may lead to 646silent codegen errors or spurious uninitialized warnings@. 647 648@item @code{TODO_update_ssa_only_virtuals}. Passes that update the 649SSA form on their own may want to delegate the updating of 650virtual names to the generic updater. Since FUD chains are 651easier to maintain, this simplifies the work they need to do. 652NOTE: If this flag is used, any OLD->NEW mappings for real names 653are explicitly destroyed and only the symbols marked for 654renaming are processed@. 655@end itemize 656 657@subsection Preserving the virtual SSA form 658@cindex preserving virtual SSA form 659 660The virtual SSA form is harder to preserve than the non-virtual SSA form 661mainly because the set of virtual operands for a statement may change at 662what some would consider unexpected times. In general, statement 663modifications should be bracketed between calls to 664@code{push_stmt_changes} and @code{pop_stmt_changes}. For example, 665 666@smallexample 667 munge_stmt (tree stmt) 668 @{ 669 push_stmt_changes (&stmt); 670 @dots{} rewrite STMT @dots{} 671 pop_stmt_changes (&stmt); 672 @} 673@end smallexample 674 675The call to @code{push_stmt_changes} saves the current state of the 676statement operands and the call to @code{pop_stmt_changes} compares 677the saved state with the current one and does the appropriate symbol 678marking for the SSA renamer. 679 680It is possible to modify several statements at a time, provided that 681@code{push_stmt_changes} and @code{pop_stmt_changes} are called in 682LIFO order, as when processing a stack of statements. 683 684Additionally, if the pass discovers that it did not need to make 685changes to the statement after calling @code{push_stmt_changes}, it 686can simply discard the topmost change buffer by calling 687@code{discard_stmt_changes}. This will avoid the expensive operand 688re-scan operation and the buffer comparison that determines if symbols 689need to be marked for renaming. 690 691@subsection Examining @code{SSA_NAME} nodes 692@cindex examining SSA_NAMEs 693 694The following macros can be used to examine @code{SSA_NAME} nodes 695 696@defmac SSA_NAME_DEF_STMT (@var{var}) 697Returns the statement @var{s} that creates the @code{SSA_NAME} 698@var{var}. If @var{s} is an empty statement (i.e., @code{IS_EMPTY_STMT 699(@var{s})} returns @code{true}), it means that the first reference to 700this variable is a USE or a VUSE@. 701@end defmac 702 703@defmac SSA_NAME_VERSION (@var{var}) 704Returns the version number of the @code{SSA_NAME} object @var{var}. 705@end defmac 706 707 708@subsection Walking the dominator tree 709 710@deftypefn {Tree SSA function} void walk_dominator_tree (@var{walk_data}, @var{bb}) 711 712This function walks the dominator tree for the current CFG calling a 713set of callback functions defined in @var{struct dom_walk_data} in 714@file{domwalk.h}. The call back functions you need to define give you 715hooks to execute custom code at various points during traversal: 716 717@enumerate 718@item Once to initialize any local data needed while processing 719@var{bb} and its children. This local data is pushed into an 720internal stack which is automatically pushed and popped as the 721walker traverses the dominator tree. 722 723@item Once before traversing all the statements in the @var{bb}. 724 725@item Once for every statement inside @var{bb}. 726 727@item Once after traversing all the statements and before recursing 728into @var{bb}'s dominator children. 729 730@item It then recurses into all the dominator children of @var{bb}. 731 732@item After recursing into all the dominator children of @var{bb} it 733can, optionally, traverse every statement in @var{bb} again 734(i.e., repeating steps 2 and 3). 735 736@item Once after walking the statements in @var{bb} and @var{bb}'s 737dominator children. At this stage, the block local data stack 738is popped. 739@end enumerate 740@end deftypefn 741 742@node Alias analysis 743@section Alias analysis 744@cindex alias 745@cindex flow-sensitive alias analysis 746@cindex flow-insensitive alias analysis 747 748Alias analysis in GIMPLE SSA form consists of two pieces. First 749the virtual SSA web ties conflicting memory accesses and provides 750a SSA use-def chain and SSA immediate-use chains for walking 751possibly dependent memory accesses. Second an alias-oracle can 752be queried to disambiguate explicit and implicit memory references. 753 754@enumerate 755@item Memory SSA form. 756 757All statements that may use memory have exactly one accompanied use of 758a virtual SSA name that represents the state of memory at the 759given point in the IL. 760 761All statements that may define memory have exactly one accompanied 762definition of a virtual SSA name using the previous state of memory 763and defining the new state of memory after the given point in the IL. 764 765@smallexample 766int i; 767int foo (void) 768@{ 769 # .MEM_3 = VDEF <.MEM_2(D)> 770 i = 1; 771 # VUSE <.MEM_3> 772 return i; 773@} 774@end smallexample 775 776The virtual SSA names in this case are @code{.MEM_2(D)} and 777@code{.MEM_3}. The store to the global variable @code{i} 778defines @code{.MEM_3} invalidating @code{.MEM_2(D)}. The 779load from @code{i} uses that new state @code{.MEM_3}. 780 781The virtual SSA web serves as constraints to SSA optimizers 782preventing illegitimate code-motion and optimization. It 783also provides a way to walk related memory statements. 784 785@item Points-to and escape analysis. 786 787Points-to analysis builds a set of constraints from the GIMPLE 788SSA IL representing all pointer operations and facts we do 789or do not know about pointers. Solving this set of constraints 790yields a conservatively correct solution for each pointer 791variable in the program (though we are only interested in 792SSA name pointers) as to what it may possibly point to. 793 794This points-to solution for a given SSA name pointer is stored 795in the @code{pt_solution} sub-structure of the 796@code{SSA_NAME_PTR_INFO} record. The following accessor 797functions are available: 798 799@itemize @bullet 800@item @code{pt_solution_includes} 801@item @code{pt_solutions_intersect} 802@end itemize 803 804Points-to analysis also computes the solution for two special 805set of pointers, @code{ESCAPED} and @code{CALLUSED}. Those 806represent all memory that has escaped the scope of analysis 807or that is used by pure or nested const calls. 808 809@item Type-based alias analysis 810 811Type-based alias analysis is frontend dependent though generic 812support is provided by the middle-end in @code{alias.c}. TBAA 813code is used by both tree optimizers and RTL optimizers. 814 815Every language that wishes to perform language-specific alias analysis 816should define a function that computes, given a @code{tree} 817node, an alias set for the node. Nodes in different alias sets are not 818allowed to alias. For an example, see the C front-end function 819@code{c_get_alias_set}. 820 821@item Tree alias-oracle 822 823The tree alias-oracle provides means to disambiguate two memory 824references and memory references against statements. The following 825queries are available: 826 827@itemize @bullet 828@item @code{refs_may_alias_p} 829@item @code{ref_maybe_used_by_stmt_p} 830@item @code{stmt_may_clobber_ref_p} 831@end itemize 832 833In addition to those two kind of statement walkers are available 834walking statements related to a reference ref. 835@code{walk_non_aliased_vuses} walks over dominating memory defining 836statements and calls back if the statement does not clobber ref 837providing the non-aliased VUSE. The walk stops at 838the first clobbering statement or if asked to. 839@code{walk_aliased_vdefs} walks over dominating memory defining 840statements and calls back on each statement clobbering ref 841providing its aliasing VDEF. The walk stops if asked to. 842 843@end enumerate 844 845 846@node Memory model 847@section Memory model 848@cindex memory model 849 850The memory model used by the middle-end models that of the C/C++ 851languages. The middle-end has the notion of an effective type 852of a memory region which is used for type-based alias analysis. 853 854The following is a refinement of ISO C99 6.5/6, clarifying the block copy case 855to follow common sense and extending the concept of a dynamic effective 856type to objects with a declared type as required for C++. 857 858@smallexample 859The effective type of an object for an access to its stored value is 860the declared type of the object or the effective type determined by 861a previous store to it. If a value is stored into an object through 862an lvalue having a type that is not a character type, then the 863type of the lvalue becomes the effective type of the object for that 864access and for subsequent accesses that do not modify the stored value. 865If a value is copied into an object using @code{memcpy} or @code{memmove}, 866or is copied as an array of character type, then the effective type 867of the modified object for that access and for subsequent accesses that 868do not modify the value is undetermined. For all other accesses to an 869object, the effective type of the object is simply the type of the 870lvalue used for the access. 871@end smallexample 872 873