1@c Copyright (C) 2004-2020 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_STMT} 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_IMM_USE_STMT (iterator); 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{gimple_set_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 Examining @code{SSA_NAME} nodes 658@cindex examining SSA_NAMEs 659 660The following macros can be used to examine @code{SSA_NAME} nodes 661 662@defmac SSA_NAME_DEF_STMT (@var{var}) 663Returns the statement @var{s} that creates the @code{SSA_NAME} 664@var{var}. If @var{s} is an empty statement (i.e., @code{IS_EMPTY_STMT 665(@var{s})} returns @code{true}), it means that the first reference to 666this variable is a USE or a VUSE@. 667@end defmac 668 669@defmac SSA_NAME_VERSION (@var{var}) 670Returns the version number of the @code{SSA_NAME} object @var{var}. 671@end defmac 672 673 674@subsection Walking the dominator tree 675 676@deftypefn {Tree SSA function} void walk_dominator_tree (@var{walk_data}, @var{bb}) 677 678This function walks the dominator tree for the current CFG calling a 679set of callback functions defined in @var{struct dom_walk_data} in 680@file{domwalk.h}. The call back functions you need to define give you 681hooks to execute custom code at various points during traversal: 682 683@enumerate 684@item Once to initialize any local data needed while processing 685@var{bb} and its children. This local data is pushed into an 686internal stack which is automatically pushed and popped as the 687walker traverses the dominator tree. 688 689@item Once before traversing all the statements in the @var{bb}. 690 691@item Once for every statement inside @var{bb}. 692 693@item Once after traversing all the statements and before recursing 694into @var{bb}'s dominator children. 695 696@item It then recurses into all the dominator children of @var{bb}. 697 698@item After recursing into all the dominator children of @var{bb} it 699can, optionally, traverse every statement in @var{bb} again 700(i.e., repeating steps 2 and 3). 701 702@item Once after walking the statements in @var{bb} and @var{bb}'s 703dominator children. At this stage, the block local data stack 704is popped. 705@end enumerate 706@end deftypefn 707 708@node Alias analysis 709@section Alias analysis 710@cindex alias 711@cindex flow-sensitive alias analysis 712@cindex flow-insensitive alias analysis 713 714Alias analysis in GIMPLE SSA form consists of two pieces. First 715the virtual SSA web ties conflicting memory accesses and provides 716a SSA use-def chain and SSA immediate-use chains for walking 717possibly dependent memory accesses. Second an alias-oracle can 718be queried to disambiguate explicit and implicit memory references. 719 720@enumerate 721@item Memory SSA form. 722 723All statements that may use memory have exactly one accompanied use of 724a virtual SSA name that represents the state of memory at the 725given point in the IL. 726 727All statements that may define memory have exactly one accompanied 728definition of a virtual SSA name using the previous state of memory 729and defining the new state of memory after the given point in the IL. 730 731@smallexample 732int i; 733int foo (void) 734@{ 735 # .MEM_3 = VDEF <.MEM_2(D)> 736 i = 1; 737 # VUSE <.MEM_3> 738 return i; 739@} 740@end smallexample 741 742The virtual SSA names in this case are @code{.MEM_2(D)} and 743@code{.MEM_3}. The store to the global variable @code{i} 744defines @code{.MEM_3} invalidating @code{.MEM_2(D)}. The 745load from @code{i} uses that new state @code{.MEM_3}. 746 747The virtual SSA web serves as constraints to SSA optimizers 748preventing illegitimate code-motion and optimization. It 749also provides a way to walk related memory statements. 750 751@item Points-to and escape analysis. 752 753Points-to analysis builds a set of constraints from the GIMPLE 754SSA IL representing all pointer operations and facts we do 755or do not know about pointers. Solving this set of constraints 756yields a conservatively correct solution for each pointer 757variable in the program (though we are only interested in 758SSA name pointers) as to what it may possibly point to. 759 760This points-to solution for a given SSA name pointer is stored 761in the @code{pt_solution} sub-structure of the 762@code{SSA_NAME_PTR_INFO} record. The following accessor 763functions are available: 764 765@itemize @bullet 766@item @code{pt_solution_includes} 767@item @code{pt_solutions_intersect} 768@end itemize 769 770Points-to analysis also computes the solution for two special 771set of pointers, @code{ESCAPED} and @code{CALLUSED}. Those 772represent all memory that has escaped the scope of analysis 773or that is used by pure or nested const calls. 774 775@item Type-based alias analysis 776 777Type-based alias analysis is frontend dependent though generic 778support is provided by the middle-end in @code{alias.c}. TBAA 779code is used by both tree optimizers and RTL optimizers. 780 781Every language that wishes to perform language-specific alias analysis 782should define a function that computes, given a @code{tree} 783node, an alias set for the node. Nodes in different alias sets are not 784allowed to alias. For an example, see the C front-end function 785@code{c_get_alias_set}. 786 787@item Tree alias-oracle 788 789The tree alias-oracle provides means to disambiguate two memory 790references and memory references against statements. The following 791queries are available: 792 793@itemize @bullet 794@item @code{refs_may_alias_p} 795@item @code{ref_maybe_used_by_stmt_p} 796@item @code{stmt_may_clobber_ref_p} 797@end itemize 798 799In addition to those two kind of statement walkers are available 800walking statements related to a reference ref. 801@code{walk_non_aliased_vuses} walks over dominating memory defining 802statements and calls back if the statement does not clobber ref 803providing the non-aliased VUSE. The walk stops at 804the first clobbering statement or if asked to. 805@code{walk_aliased_vdefs} walks over dominating memory defining 806statements and calls back on each statement clobbering ref 807providing its aliasing VDEF. The walk stops if asked to. 808 809@end enumerate 810 811 812@node Memory model 813@section Memory model 814@cindex memory model 815 816The memory model used by the middle-end models that of the C/C++ 817languages. The middle-end has the notion of an effective type 818of a memory region which is used for type-based alias analysis. 819 820The following is a refinement of ISO C99 6.5/6, clarifying the block copy case 821to follow common sense and extending the concept of a dynamic effective 822type to objects with a declared type as required for C++. 823 824@smallexample 825The effective type of an object for an access to its stored value is 826the declared type of the object or the effective type determined by 827a previous store to it. If a value is stored into an object through 828an lvalue having a type that is not a character type, then the 829type of the lvalue becomes the effective type of the object for that 830access and for subsequent accesses that do not modify the stored value. 831If a value is copied into an object using @code{memcpy} or @code{memmove}, 832or is copied as an array of character type, then the effective type 833of the modified object for that access and for subsequent accesses that 834do not modify the value is undetermined. For all other accesses to an 835object, the effective type of the object is simply the type of the 836lvalue used for the access. 837@end smallexample 838 839