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