ression whose arguments are `reg' or `match_scratch' (*note RTL Template::) expressions, the combiner phase can add the appropriate `clobber' expressions to an insn it has constructed when doing so will cause a pattern to be matched. This feature can be used, for example, on a machine that whose multiply and add instructions don't use an MQ register but which has an add-accumulate instruction that does clobber the MQ register. Similarly, a combined instruction might require a temporary register while the constituent instructions might not. When a `clobber' expression for a register appears inside a `parallel' with other side effects, the register allocator guarantees that the register is unoccupied both before and after that insn. However, the reload phase may allocate a register used for one of the inputs unless the `&' constraint is specified for the selected alternative (*note Modifiers::). You can clobber either a specific hard register, a pseudo register, or a `scratch' expression; in the latter two cases, GCC will allocate a hard register that is available there for use as a temporary. For instructions that require a temporary register, you should use `scratch' instead of a pseudo-register because this will allow the combiner phase to add the `clobber' when required. You do this by coding (`clobber' (`match_scratch' ...)). If you do clobber a pseudo register, use one which appears nowhere else--generate a new one each time. Otherwise, you may confuse CSE. There is one other known use for clobbering a pseudo register in a `parallel': when one of the input operands of the insn is also clobbered by the insn. In this case, using the same pseudo register in the clobber and elsewhere in the insn produces the expected results. `(use X)' Represents the use of the value of X. It indicates that the value in X at this point in the program is needed, even though it may not be apparent why this is so. Therefore, the compiler will not attempt to delete previous instructions whose only effect is to store a value in X. X must be a `reg' expression. In some situations, it may be tempting to add a `use' of a register in a `parallel' to describe a situation where the value of a special register will modify the behavior of the instruction. An hypothetical example might be a pattern for an addition that can either wrap around or use saturating addition depending on the value of a special control register: (parallel [(set (reg:SI 2) (unspec:SI [(reg:SI 3) (reg:SI 4)] 0)) (use (reg:SI 1))]) This will not work, several of the optimizers only look at expressions locally; it is very likely that if you have multiple insns with identical inputs to the `unspec', they will be optimized away even if register 1 changes in between. This means that `use' can _only_ be used to describe that the register is live. You should think twice before adding `use' statements, more often you will want to use `unspec' instead. The `use' RTX is most commonly useful to describe that a fixed register is implicitly used in an insn. It is also safe to use in patterns where the compiler knows for other reasons that the result of the whole pattern is variable, such as `movmemM' or `call' patterns. During the reload phase, an insn that has a `use' as pattern can carry a reg_equal note. These `use' insns will be deleted before the reload phase exits. During the delayed branch scheduling phase, X may be an insn. This indicates that X previously was located at this place in the code and its data dependencies need to be taken into account. These `use' insns will be deleted before the delayed branch scheduling phase exits. `(parallel [X0 X1 ...])' Represents several side effects performed in parallel. The square brackets stand for a vector; the operand of `parallel' is a vector of expressions. X0, X1 and so on are individual side effect expressions--expressions of code `set', `call', `return', `clobber' or `use'. "In parallel" means that first all the values used in the individual side-effects are computed, and second all the actual side-effects are performed. For example, (parallel [(set (reg:SI 1) (mem:SI (reg:SI 1))) (set (mem:SI (reg:SI 1)) (reg:SI 1))]) says unambiguously that the values of hard register 1 and the memory location addressed by it are interchanged. In both places where `(reg:SI 1)' appears as a memory address it refers to the value in register 1 _before_ the execution of the insn. It follows that it is _incorrect_ to use `parallel' and expect the result of one `set' to be available for the next one. For example, people sometimes attempt to represent a jump-if-zero instruction this way: (parallel [(set (cc0) (reg:SI 34)) (set (pc) (if_then_else (eq (cc0) (const_int 0)) (label_ref ...) (pc)))]) But this is incorrect, because it says that the jump condition depends on the condition code value _before_ this instruction, not on the new value that is set by this instruction. Peephole optimization, which takes place together with final assembly code output, can produce insns whose patterns consist of a `parallel' whose elements are the operands needed to output the resulting assembler code--often `reg', `mem' or constant expressions. This would not be well-formed RTL at any other stage in compilation, but it is ok then because no further optimization remains to be done. However, the definition of the macro `NOTICE_UPDATE_CC', if any, must deal with such insns if you define any peephole optimizations. `(cond_exec [COND EXPR])' Represents a conditionally executed expression. The EXPR is executed only if the COND is nonzero. The COND expression must not have side-effects, but the EXPR may very well have side-effects. `(sequence [INSNS ...])' Represents a sequence of insns. Each of the INSNS that appears in the vector is suitable for appearing in the chain of insns, so it must be an `insn', `jump_insn', `call_insn', `code_label', `barrier' or `note'. A `sequence' RTX is never placed in an actual insn during RTL generation. It represents the sequence of insns that result from a `define_expand' _before_ those insns are passed to `emit_insn' to insert them in the chain of insns. When actually inserted, the individual sub-insns are separated out and the `sequence' is forgotten. After delay-slot scheduling is completed, an insn and all the insns that reside in its delay slots are grouped together into a `sequence'. The insn requiring the delay slot is the first insn in the vector; subsequent insns are to be placed in the delay slot. `INSN_ANNULLED_BRANCH_P' is set on an insn in a delay slot to indicate that a branch insn should be used that will conditionally annul the effect of the insns in the delay slots. In such a case, `INSN_FROM_TARGET_P' indicates that the insn is from the target of the branch and should be executed only if the branch is taken; otherwise the insn should be executed only if the branch is not taken. *Note Delay Slots::. These expression codes appear in place of a side effect, as the body of an insn, though strictly speaking they do not always describe side effects as such: `(asm_input S)' Represents literal assembler code as described by the string S. `(unspec [OPERANDS ...] INDEX)' `(unspec_volatile [OPERANDS ...] INDEX)' Represents a machine-specific operation on OPERANDS. INDEX selects between multiple machine-specific operations. `unspec_volatile' is used for volatile operations and operations that may trap; `unspec' is used for other operations. These codes may appear inside a `pattern' of an insn, inside a `parallel', or inside an expression. `(addr_vec:M [LR0 LR1 ...])' Represents a table of jump addresses. The vector elements LR0, etc., are `label_ref' expressions. The mode M specifies how much space is given to each address; normally M would be `Pmode'. `(addr_diff_vec:M BASE [LR0 LR1 ...] MIN MAX FLAGS)' Represents a table of jump addresses expressed as offsets from BASE. The vector elements LR0, etc., are `label_ref' expressions and so is BASE. The mode M specifies how much space is given to each address-difference. MIN and MAX are set up by branch shortening and hold a label with a minimum and a maximum address, respectively. FLAGS indicates the relative position of BASE, MIN and MAX to the containing insn and of MIN and MAX to BASE. See rtl.def for details. `(prefetch:M ADDR RW LOCALITY)' Represents prefetch of memory at address ADDR. Operand RW is 1 if the prefetch is for data to be written, 0 otherwise; targets that do not support write prefetches should treat this as a normal prefetch. Operand LOCALITY specifies the amount of temporal locality; 0 if there is none or 1, 2, or 3 for increasing levels of temporal locality; targets that do not support locality hints should ignore this. This insn is used to minimize cache-miss latency by moving data into a cache before it is accessed. It should use only non-faulting data prefetch instructions.  File: gccint.info, Node: Incdec, Next: Assembler, Prev: Side Effects, Up: RTL 12.16 Embedded Side-Effects on Addresses ======================================== Six special side-effect expression codes appear as memory addresses. `(pre_dec:M X)' Represents the side effect of decrementing X by a standard amount and represents also the value that X has after being decremented. X must be a `reg' or `mem', but most machines allow only a `reg'. M must be the machine mode for pointers on the machine in use. The amount X is decremented by is the length in bytes of the machine mode of the containing memory reference of which this expression serves as the address. Here is an example of its use: (mem:DF (pre_dec:SI (reg:SI 39))) This says to decrement pseudo register 39 by the length of a `DFmode' value and use the result to address a `DFmode' value. `(pre_inc:M X)' Similar, but specifies incrementing X instead of decrementing it. `(post_dec:M X)' Represents the same side effect as `pre_dec' but a different value. The value represented here is the value X has before being decremented. `(post_inc:M X)' Similar, but specifies incrementing X instead of decrementing it. `(post_modify:M X Y)' Represents the side effect of setting X to Y and represents X before X is modified. X must be a `reg' or `mem', but most machines allow only a `reg'. M must be the machine mode for pointers on the machine in use. The expression Y must be one of three forms: `(plus:M X Z)', `(minus:M X Z)', or `(plus:M X I)', where Z is an index register and I is a constant. Here is an example of its use: (mem:SF (post_modify:SI (reg:SI 42) (plus (reg:SI 42) (reg:SI 48)))) This says to modify pseudo register 42 by adding the contents of pseudo register 48 to it, after the use of what ever 42 points to. `(pre_modify:M X EXPR)' Similar except side effects happen before the use. These embedded side effect expressions must be used with care. Instruction patterns may not use them. Until the `flow' pass of the compiler, they may occur only to represent pushes onto the stack. The `flow' pass finds cases where registers are incremented or decremented in one instruction and used as an address shortly before or after; these cases are then transformed to use pre- or post-increment or -decrement. If a register used as the operand of these expressions is used in another address in an insn, the original value of the register is used. Uses of the register outside of an address are not permitted within the same insn as a use in an embedded side effect expression because such insns behave differently on different machines and hence must be treated as ambiguous and disallowed. An instruction that can be represented with an embedded side effect could also be represented using `parallel' containing an additional `set' to describe how the address register is altered. This is not done because machines that allow these operations at all typically allow them wherever a memory address is called for. Describing them as additional parallel stores would require doubling the number of entries in the machine description.  File: gccint.info, Node: Assembler, Next: Insns, Prev: Incdec, Up: RTL 12.17 Assembler Instructions as Expressions =========================================== The RTX code `asm_operands' represents a value produced by a user-specified assembler instruction. It is used to represent an `asm' statement with arguments. An `asm' statement with a single output operand, like this: asm ("foo %1,%2,%0" : "=a" (outputvar) : "g" (x + y), "di" (*z)); is represented using a single `asm_operands' RTX which represents the value that is stored in `outputvar': (set RTX-FOR-OUTPUTVAR (asm_operands "foo %1,%2,%0" "a" 0 [RTX-FOR-ADDITION-RESULT RTX-FOR-*Z] [(asm_input:M1 "g") (asm_input:M2 "di")])) Here the operands of the `asm_operands' RTX are the assembler template string, the output-operand's constraint, the index-number of the output operand among the output operands specified, a vector of input operand RTX's, and a vector of input-operand modes and constraints. The mode M1 is the mode of the sum `x+y'; M2 is that of `*z'. When an `asm' statement has multiple output values, its insn has several such `set' RTX's inside of a `parallel'. Each `set' contains a `asm_operands'; all of these share the same assembler template and vectors, but each contains the constraint for the respective output operand. They are also distinguished by the output-operand index number, which is 0, 1, ... for successive output operands.  File: gccint.info, Node: Insns, Next: Calls, Prev: Assembler, Up: RTL 12.18 Insns =========== The RTL representation of the code for a function is a doubly-linked chain of objects called "insns". Insns are expressions with special codes that are used for no other purpose. Some insns are actual instructions; others represent dispatch tables for `switch' statements; others represent labels to jump to or various sorts of declarative information. In addition to its own specific data, each insn must have a unique id-number that distinguishes it from all other insns in the current function (after delayed branch scheduling, copies of an insn with the same id-number may be present in multiple places in a function, but these copies will always be identical and will only appear inside a `sequence'), and chain pointers to the preceding and following insns. These three fields occupy the same position in every insn, independent of the expression code of the insn. They could be accessed with `XEXP' and `XINT', but instead three special macros are always used: `INSN_UID (I)' Accesses the unique id of insn I. `PREV_INSN (I)' Accesses the chain pointer to the insn preceding I. If I is the first insn, this is a null pointer. `NEXT_INSN (I)' Accesses the chain pointer to the insn following I. If I is the last insn, this is a null pointer. The first insn in the chain is obtained by calling `get_insns'; the last insn is the result of calling `get_last_insn'. Within the chain delimited by these insns, the `NEXT_INSN' and `PREV_INSN' pointers must always correspond: if INSN is not the first insn, NEXT_INSN (PREV_INSN (INSN)) == INSN is always true and if INSN is not the last insn, PREV_INSN (NEXT_INSN (INSN)) == INSN is always true. After delay slot scheduling, some of the insns in the chain might be `sequence' expressions, which contain a vector of insns. The value of `NEXT_INSN' in all but the last of these insns is the next insn in the vector; the value of `NEXT_INSN' of the last insn in the vector is the same as the value of `NEXT_INSN' for the `sequence' in which it is contained. Similar rules apply for `PREV_INSN'. This means that the above invariants are not necessarily true for insns inside `sequence' expressions. Specifically, if INSN is the first insn in a `sequence', `NEXT_INSN (PREV_INSN (INSN))' is the insn containing the `sequence' expression, as is the value of `PREV_INSN (NEXT_INSN (INSN))' if INSN is the last insn in the `sequence' expression. You can use these expressions to find the containing `sequence' expression. Every insn has one of the following six expression codes: `insn' The expression code `insn' is used for instructions that do not jump and do not do function calls. `sequence' expressions are always contained in insns with code `insn' even if one of those insns should jump or do function calls. Insns with code `insn' have four additional fields beyond the three mandatory ones listed above. These four are described in a table below. `jump_insn' The expression code `jump_insn' is used for instructions that may jump (or, more generally, may contain `label_ref' expressions to which `pc' can be set in that instruction). If there is an instruction to return from the current function, it is recorded as a `jump_insn'. `jump_insn' insns have the same extra fields as `insn' insns, accessed in the same way and in addition contain a field `JUMP_LABEL' which is defined once jump optimization has completed. For simple conditional and unconditional jumps, this field contains the `code_label' to which this insn will (possibly conditionally) branch. In a more complex jump, `JUMP_LABEL' records one of the labels that the insn refers to; other jump target labels are recorded as `REG_LABEL_TARGET' notes. The exception is `addr_vec' and `addr_diff_vec', where `JUMP_LABEL' is `NULL_RTX' and the only way to find the labels is to scan the entire body of the insn. Return insns count as jumps, but since they do not refer to any labels, their `JUMP_LABEL' is `NULL_RTX'. `call_insn' The expression code `call_insn' is used for instructions that may do function calls. It is important to distinguish these instructions because they imply that certain registers and memory locations may be altered unpredictably. `call_insn' insns have the same extra fields as `insn' insns, accessed in the same way and in addition contain a field `CALL_INSN_FUNCTION_USAGE', which contains a list (chain of `expr_list' expressions) containing `use' and `clobber' expressions that denote hard registers and `MEM's used or clobbered by the called function. A `MEM' generally points to a stack slots in which arguments passed to the libcall by reference (*note TARGET_PASS_BY_REFERENCE: Register Arguments.) are stored. If the argument is caller-copied (*note TARGET_CALLEE_COPIES: Register Arguments.), the stack slot will be mentioned in `CLOBBER' and `USE' entries; if it's callee-copied, only a `USE' will appear, and the `MEM' may point to addresses that are not stack slots. `CLOBBER'ed registers in this list augment registers specified in `CALL_USED_REGISTERS' (*note Register Basics::). `code_label' A `code_label' insn represents a label that a jump insn can jump to. It contains two special fields of data in addition to the three standard ones. `CODE_LABEL_NUMBER' is used to hold the "label number", a number that identifies this label uniquely among all the labels in the compilation (not just in the current function). Ultimately, the label is represented in the assembler output as an assembler label, usually of the form `LN' where N is the label number. When a `code_label' appears in an RTL expression, it normally appears within a `label_ref' which represents the address of the label, as a number. Besides as a `code_label', a label can also be represented as a `note' of type `NOTE_INSN_DELETED_LABEL'. The field `LABEL_NUSES' is only defined once the jump optimization phase is completed. It contains the number of times this label is referenced in the current function. The field `LABEL_KIND' differentiates four different types of labels: `LABEL_NORMAL', `LABEL_STATIC_ENTRY', `LABEL_GLOBAL_ENTRY', and `LABEL_WEAK_ENTRY'. The only labels that do not have type `LABEL_NORMAL' are "alternate entry points" to the current function. These may be static (visible only in the containing translation unit), global (exposed to all translation units), or weak (global, but can be overridden by another symbol with the same name). Much of the compiler treats all four kinds of label identically. Some of it needs to know whether or not a label is an alternate entry point; for this purpose, the macro `LABEL_ALT_ENTRY_P' is provided. It is equivalent to testing whether `LABEL_KIND (label) == LABEL_NORMAL'. The only place that cares about the distinction between static, global, and weak alternate entry points, besides the front-end code that creates them, is the function `output_alternate_entry_point', in `final.c'. To set the kind of a label, use the `SET_LABEL_KIND' macro. `barrier' Barriers are placed in the instruction stream when control cannot flow past them. They are placed after unconditional jump instructions to indicate that the jumps are unconditional and after calls to `volatile' functions, which do not return (e.g., `exit'). They contain no information beyond the three standard fields. `note' `note' insns are used to represent additional debugging and declarative information. They contain two nonstandard fields, an integer which is accessed with the macro `NOTE_LINE_NUMBER' and a string accessed with `NOTE_SOURCE_FILE'. If `NOTE_LINE_NUMBER' is positive, the note represents the position of a source line and `NOTE_SOURCE_FILE' is the source file name that the line came from. These notes control generation of line number data in the assembler output. Otherwise, `NOTE_LINE_NUMBER' is not really a line number but a code with one of the following values (and `NOTE_SOURCE_FILE' must contain a null pointer): `NOTE_INSN_DELETED' Such a note is completely ignorable. Some passes of the compiler delete insns by altering them into notes of this kind. `NOTE_INSN_DELETED_LABEL' This marks what used to be a `code_label', but was not used for other purposes than taking its address and was transformed to mark that no code jumps to it. `NOTE_INSN_BLOCK_BEG' `NOTE_INSN_BLOCK_END' These types of notes indicate the position of the beginning and end of a level of scoping of variable names. They control the output of debugging information. `NOTE_INSN_EH_REGION_BEG' `NOTE_INSN_EH_REGION_END' These types of notes indicate the position of the beginning and end of a level of scoping for exception handling. `NOTE_BLOCK_NUMBER' identifies which `CODE_LABEL' or `note' of type `NOTE_INSN_DELETED_LABEL' is associated with the given region. `NOTE_INSN_LOOP_BEG' `NOTE_INSN_LOOP_END' These types of notes indicate the position of the beginning and end of a `while' or `for' loop. They enable the loop optimizer to find loops quickly. `NOTE_INSN_LOOP_CONT' Appears at the place in a loop that `continue' statements jump to. `NOTE_INSN_LOOP_VTOP' This note indicates the place in a loop where the exit test begins for those loops in which the exit test has been duplicated. This position becomes another virtual start of the loop when considering loop invariants. `NOTE_INSN_FUNCTION_BEG' Appears at the start of the function body, after the function prologue. These codes are printed symbolically when they appear in debugging dumps. The machine mode of an insn is normally `VOIDmode', but some phases use the mode for various purposes. The common subexpression elimination pass sets the mode of an insn to `QImode' when it is the first insn in a block that has already been processed. The second Haifa scheduling pass, for targets that can multiple issue, sets the mode of an insn to `TImode' when it is believed that the instruction begins an issue group. That is, when the instruction cannot issue simultaneously with the previous. This may be relied on by later passes, in particular machine-dependent reorg. Here is a table of the extra fields of `insn', `jump_insn' and `call_insn' insns: `PATTERN (I)' An expression for the side effect performed by this insn. This must be one of the following codes: `set', `call', `use', `clobber', `return', `asm_input', `asm_output', `addr_vec', `addr_diff_vec', `trap_if', `unspec', `unspec_volatile', `parallel', `cond_exec', or `sequence'. If it is a `parallel', each element of the `parallel' must be one these codes, except that `parallel' expressions cannot be nested and `addr_vec' and `addr_diff_vec' are not permitted inside a `parallel' expression. `INSN_CODE (I)' An integer that says which pattern in the machine description matches this insn, or -1 if the matching has not yet been attempted. Such matching is never attempted and this field remains -1 on an insn whose pattern consists of a single `use', `clobber', `asm_input', `addr_vec' or `addr_diff_vec' expression. Matching is also never attempted on insns that result from an `asm' statement. These contain at least one `asm_operands' expression. The function `asm_noperands' returns a non-negative value for such insns. In the debugging output, this field is printed as a number followed by a symbolic representation that locates the pattern in the `md' file as some small positive or negative offset from a named pattern. `LOG_LINKS (I)' A list (chain of `insn_list' expressions) giving information about dependencies between instructions within a basic block. Neither a jump nor a label may come between the related insns. These are only used by the schedulers and by combine. This is a deprecated data structure. Def-use and use-def chains are now preferred. `REG_NOTES (I)' A list (chain of `expr_list' and `insn_list' expressions) giving miscellaneous information about the insn. It is often information pertaining to the registers used in this insn. The `LOG_LINKS' field of an insn is a chain of `insn_list' expressions. Each of these has two operands: the first is an insn, and the second is another `insn_list' expression (the next one in the chain). The last `insn_list' in the chain has a null pointer as second operand. The significant thing about the chain is which insns appear in it (as first operands of `insn_list' expressions). Their order is not significant. This list is originally set up by the flow analysis pass; it is a null pointer until then. Flow only adds links for those data dependencies which can be used for instruction combination. For each insn, the flow analysis pass adds a link to insns which store into registers values that are used for the first time in this insn. The `REG_NOTES' field of an insn is a chain similar to the `LOG_LINKS' field but it includes `expr_list' expressions in addition to `insn_list' expressions. There are several kinds of register notes, which are distinguished by the machine mode, which in a register note is really understood as being an `enum reg_note'. The first operand OP of the note is data whose meaning depends on the kind of note. The macro `REG_NOTE_KIND (X)' returns the kind of register note. Its counterpart, the macro `PUT_REG_NOTE_KIND (X, NEWKIND)' sets the register note type of X to be NEWKIND. Register notes are of three classes: They may say something about an input to an insn, they may say something about an output of an insn, or they may create a linkage between two insns. There are also a set of values that are only used in `LOG_LINKS'. These register notes annotate inputs to an insn: `REG_DEAD' The value in OP dies in this insn; that is to say, altering the value immediately after this insn would not affect the future behavior of the program. It does not follow that the register OP has no useful value after this insn since OP is not necessarily modified by this insn. Rather, no subsequent instruction uses the contents of OP. `REG_UNUSED' The register OP being set by this insn will not be used in a subsequent insn. This differs from a `REG_DEAD' note, which indicates that the value in an input will not be used subsequently. These two notes are independent; both may be present for the same register. `REG_INC' The register OP is incremented (or decremented; at this level there is no distinction) by an embedded side effect inside this insn. This means it appears in a `post_inc', `pre_inc', `post_dec' or `pre_dec' expression. `REG_NONNEG' The register OP is known to have a nonnegative value when this insn is reached. This is used so that decrement and branch until zero instructions, such as the m68k dbra, can be matched. The `REG_NONNEG' note is added to insns only if the machine description has a `decrement_and_branch_until_zero' pattern. `REG_NO_CONFLICT' This insn does not cause a conflict between OP and the item being set by this insn even though it might appear that it does. In other words, if the destination register and OP could otherwise be assigned the same register, this insn does not prevent that assignment. Insns with this note are usually part of a block that begins with a `clobber' insn specifying a multi-word pseudo register (which will be the output of the block), a group of insns that each set one word of the value and have the `REG_NO_CONFLICT' note attached, and a final insn that copies the output to itself with an attached `REG_EQUAL' note giving the expression being computed. This block is encapsulated with `REG_LIBCALL' and `REG_RETVAL' notes on the first and last insns, respectively. `REG_LABEL_OPERAND' This insn uses OP, a `code_label' or a `note' of type `NOTE_INSN_DELETED_LABEL', but is not a `jump_insn', or it is a `jump_insn' that refers to the operand as an ordinary operand. The label may still eventually be a jump target, but if so in an indirect jump in a subsequent insn. The presence of this note allows jump optimization to be aware that OP is, in fact, being used, and flow optimization to build an accurate flow graph. `REG_LABEL_TARGET' This insn is a `jump_insn' but not a `addr_vec' or `addr_diff_vec'. It uses OP, a `code_label' as a direct or indirect jump target. Its purpose is similar to that of `REG_LABEL_OPERAND'. This note is only present if the insn has multiple targets; the last label in the insn (in the highest numbered insn-field) goes into the `JUMP_LABEL' field and does not have a `REG_LABEL_TARGET' note. *Note JUMP_LABEL: Insns. `REG_CROSSING_JUMP' This insn is an branching instruction (either an unconditional jump or an indirect jump) which crosses between hot and cold sections, which could potentially be very far apart in the executable. The presence of this note indicates to other optimizations that this this branching instruction should not be "collapsed" into a simpler branching construct. It is used when the optimization to partition basic blocks into hot and cold sections is turned on. `REG_SETJMP' Appears attached to each `CALL_INSN' to `setjmp' or a related function. The following notes describe attributes of outputs of an insn: `REG_EQUIV' `REG_EQUAL' This note is only valid on an insn that sets only one register and indicates that that register will be equal to OP at run time; the scope of this equivalence differs between the two types of notes. The value which the insn explicitly copies into the register may look different from OP, but they will be equal at run time. If the output of the single `set' is a `strict_low_part' expression, the note refers to the register that is contained in `SUBREG_REG' of the `subreg' expression. For `REG_EQUIV', the register is equivalent to OP throughout the entire function, and could validly be replaced in all its occurrences by OP. ("Validly" here refers to the data flow of the program; simple replacement may make some insns invalid.) For example, when a constant is loaded into a register that is never assigned any other value, this kind of note is used. When a parameter is copied into a pseudo-register at entry to a function, a note of this kind records that the register is equivalent to the stack slot where the parameter was passed. Although in this case the register may be set by other insns, it is still valid to replace the register by the stack slot throughout the function. A `REG_EQUIV' note is also used on an instruction which copies a register parameter into a pseudo-register at entry to a function, if there is a stack slot where that parameter could be stored. Although other insns may set the pseudo-register, it is valid for the compiler to replace the pseudo-register by stack slot throughout the function, provided the compiler ensures that the stack slot is properly initialized by making the replacement in the initial copy instruction as well. This is used on machines for which the calling convention allocates stack space for register parameters. See `REG_PARM_STACK_SPACE' in *note Stack Arguments::. In the case of `REG_EQUAL', the register that is set by this insn will be equal to OP at run time at the end of this insn but not necessarily elsewhere in the function. In this case, OP is typically an arithmetic expression. For example, when a sequence of insns such as a library call is used to perform an arithmetic operation, this kind of note is attached to the insn that produces or copies the final value. These two notes are used in different ways by the compiler passes. `REG_EQUAL' is used by passes prior to register allocation (such as common subexpression elimination and loop optimization) to tell them how to think of that value. `REG_EQUIV' notes are used by register allocation to indicate that there is an available substitute expression (either a constant or a `mem' expression for the location of a parameter on the stack) that may be used in place of a register if insufficient registers are available. Except for stack homes for parameters, which are indicated by a `REG_EQUIV' note and are not useful to the early optimization passes and pseudo registers that are equivalent to a memory location throughout their entire life, which is not detected until later in the compilation, all equivalences are initially indicated by an attached `REG_EQUAL' note. In the early stages of register allocation, a `REG_EQUAL' note is changed into a `REG_EQUIV' note if OP is a constant and the insn represents the only set of its destination register. Thus, compiler passes prior to register allocation need only check for `REG_EQUAL' notes and passes subsequent to register allocation need only check for `REG_EQUIV' notes. These notes describe linkages between insns. They occur in pairs: one insn has one of a pair of notes that points to a second insn, which has the inverse note pointing back to the first insn. `REG_RETVAL' This insn copies the value of a multi-insn sequence (for example, a library call), and OP is the first insn of the sequence (for a library call, the first insn that was generated to set up the arguments for the library call). Loop optimization uses this note to treat such a sequence as a single operation for code motion purposes and flow analysis uses this note to delete such sequences whose results are dead. A `REG_EQUAL' note will also usually be attached to this insn to provide the expression being computed by the sequence. These notes will be deleted after reload, since they are no longer accurate or useful. `REG_LIBCALL' This is the inverse of `REG_RETVAL': it is placed on the first insn of a multi-insn sequence, and it points to the last one. These notes are deleted after reload, since they are no longer useful or accurate. `REG_CC_SETTER' `REG_CC_USER' On machines that use `cc0', the insns which set and use `cc0' set and use `cc0' are adjacent. However, when branch delay slot filling is done, this may no longer be true. In this case a `REG_CC_USER' note will be placed on the insn setting `cc0' to point to the insn using `cc0' and a `REG_CC_SETTER' note will be placed on the insn using `cc0' to point to the insn setting `cc0'. These values are only used in the `LOG_LINKS' field, and indicate the type of dependency that each link represents. Links which indicate a data dependence (a read after write dependence) do not use any code, they simply have mode `VOIDmode', and are printed without any descriptive text. `REG_DEP_TRUE' This indicates a true dependence (a read after write dependence). `REG_DEP_OUTPUT' This indicates an output dependence (a write after write dependence). `REG_DEP_ANTI' This indicates an anti dependence (a write after read dependence). These notes describe information gathered from gcov profile data. They are stored in the `REG_NOTES' field of an insn as an `expr_list'. `REG_BR_PROB' This is used to specify the ratio of branches to non-branches of a branch insn according to the profile data. The value is stored as a value between 0 and REG_BR_PROB_BASE; larger values indicate a higher probability that the branch will be taken. `REG_BR_PRED' These notes are found in JUMP insns after delayed branch scheduling has taken place. They indicate both the direction and the likelihood of the JUMP. The format is a bitmask of ATTR_FLAG_* values. `REG_FRAME_RELATED_EXPR' This is used on an RTX_FRAME_RELATED_P insn wherein the attached expression is used in place of the actual insn pattern. This is done in cases where the pattern is either complex or misleading. `REG_LIBCALL_ID' This is used to specify that an insn is part of a libcall. Each libcall in a function has a unique id, and all the insns that are part of that libcall will have a REG_LIBCALL_ID note attached with the same ID. For convenience, the machine mode in an `insn_list' or `expr_list' is printed using these symbolic codes in debugging dumps. The only difference between the expression codes `insn_list' and `expr_list' is that the first operand of an `insn_list' is assumed to be an insn and is printed in debugging dumps as the insn's unique id; the first operand of an `expr_list' is printed in the ordinary way as an expression.  File: gccint.info, Node: Calls, Next: Sharing, Prev: Insns, Up: RTL 12.19 RTL Representation of Function-Call Insns =============================================== Insns that call subroutines have the RTL expression code `call_insn'. These insns must satisfy special rules, and their bodies must use a special RTL expression code, `call'. A `call' expression has two operands, as follows: (call (mem:FM ADDR) NBYTES) Here NBYTES is an operand that represents the number of bytes of argument data being passed to the subroutine, FM is a machine mode (which must equal as the definition of the `FUNCTION_MODE' macro in the machine description) and ADDR represents the address of the subroutine. For a subroutine that returns no value, the `call' expression as shown above is the entire body of the insn, except that the insn might also contain `use' or `clobber' expressions. For a subroutine that returns a value whose mode is not `BLKmode', the value is returned in a hard register. If this register's number is R, then the body of the call insn looks like this: (set (reg:M R) (call (mem:FM ADDR) NBYTES)) This RTL expression makes it clear (to the optimizer passes) that the appropriate register receives a useful value in this insn. When a subroutine returns a `BLKmode' value, it is handled by passing to the subroutine the address of a place to store the value. So the call insn itself does not "return" any value, and it has the same RTL form as a call that returns nothing. On some machines, the call instruction itself clobbers some register, for example to contain the return address. `call_insn' insns on these machines should have a body which is a `parallel' that contains both the `call' expression and `clobber' expressions that indicate which registers are destroyed. Similarly, if the call instruction requires some register other than the stack pointer that is not explicitly mentioned in its RTL, a `use' subexpression should mention that register. Functions that are called are assumed to modify all registers listed in the configuration macro `CALL_USED_REGISTERS' (*note Register Basics::) and, with the exception of `const' functions and library calls, to modify all of memory. Insns containing just `use' expressions directly precede the `call_insn' insn to indicate which registers contain inputs to the function. Similarly, if registers other than those in `CALL_USED_REGISTERS' are clobbered by the called function, insns containing a single `clobber' follow immediately after the call to indicate which registers.  File: gccint.info, Node: Sharing, Next: Reading RTL, Prev: Calls, Up: RTL 12.20 Structure Sharing Assumptions =================================== The compiler assumes that certain kinds of RTL expressions are unique; there do not exist two distinct objects representing the same value. In other cases, it makes an opposite assumption: that no RTL expression object of a certain kind appears in more than one place in the containing structure. These assumptions refer to a single function; except for the RTL objects that describe global variables and external functions, and a few standard objects such as small integer constants, no RTL objects are common to two functions. * Each pseudo-register has only a single `reg' object to represent it, and therefore only a single machine mode. * For any symbolic label, there is only one `symbol_ref' object referring to it. * All `const_int' expressions with equal values are shared. * There is only one `pc' expression. * There is only one `cc0' expression. * There is only one `const_double' expression with value 0 for each floating point mode. Likewise for values 1 and 2. * There is only one `const_vector' expression with value 0 for each vector mode, be it an integer or a double constant vector. * No `label_ref' or `scratch' appears in more than one place in the RTL structure; in other words, it is safe to do a tree-walk of all the insns in the function and assume that each time a `label_ref' or `scratch' is seen it is distinct from all others that are seen. * Only one `mem' object is normally created for each static variable or stack slot, so these objects are frequently shared in all the places they appear. However, separate but equal objects for these variables are occasionally made. * When a single `asm' statement has multiple output operands, a distinct `asm_operands' expression is made for each output operand. However, these all share the vector which contains the sequence of input operands. This sharing is used later on to test whether two `asm_operands' expressions come from the same statement, so all optimizations must carefully preserve the sharing if they copy the vector at all. * No RTL object appears in more than one place in the RTL structure except as described above. Many passes of the compiler rely on this by assuming that they can modify RTL objects in place without unwanted side-effects on other insns. * During initial RTL generation, shared structure is freely introduced. After all the RTL for a function has been generated, all shared structure is copied by `unshare_all_rtl' in `emit-rtl.c', after which the above rules are guaranteed to be followed. * During the combiner pass, shared structure within an insn can exist temporarily. However, the shared structure is copied before the combiner is finished with the insn. This is done by calling `copy_rtx_if_shared', which is a subroutine of `unshare_all_rtl'.  File: gccint.info, Node: Reading RTL, Prev: Sharing, Up: RTL 12.21 Reading RTL ================= To read an RTL object from a file, call `read_rtx'. It takes one argument, a stdio stream, and returns a single RTL object. This routine is defined in `read-rtl.c'. It is not available in the compiler itself, only the various programs that generate the compiler back end from the machine description. People frequently have the idea of using RTL stored as text in a file as an interface between a language front end and the bulk of GCC. This idea is not feasible. GCC was designed to use RTL internally only. Correct RTL for a given program is very dependent on the particular target machine. And the RTL does not contain all the information about the program. The proper way to interface GCC to a new language front end is with the "tree" data structure, described in the files `tree.h' and `tree.def'. The documentation for this structure (*note Trees::) is incomplete.  File: gccint.info, Node: Control Flow, Next: Loop Analysis and Representation, Prev: RTL, Up: Top 13 Control Flow Graph ********************* A control flow graph (CFG) is a data structure built on top of the intermediate code representation (the RTL or `tree' instruction stream) abstracting the control flow behavior of a function that is being compiled. The CFG is a directed graph where the vertices represent basic blocks and edges represent possible transfer of control flow from one basic block to another. The data structures used to represent the control flow graph are defined in `basic-block.h'. * Menu: * Basic Blocks:: The definition and representation of basic blocks. * Edges:: Types of edges and their representation. * Profile information:: Representation of frequencies and probabilities. * Maintaining the CFG:: Keeping the control flow graph and up to date. * Liveness information:: Using and maintaining liveness information.  File: gccint.info, Node: Basic Blocks, Next: Edges, Up: Control Flow 13.1 Basic Blocks ================= A basic block is a straight-line sequence of code with only one entry point and only one exit. In GCC, basic blocks are represented using the `basic_block' data type. Two pointer members of the `basic_block' structure are the pointers `next_bb' and `prev_bb'. These are used to keep doubly linked chain of basic blocks in the same order as the underlying instruction stream. The chain of basic blocks is updated transparently by the provided API for manipulating the CFG. The macro `FOR_EACH_BB' can be used to visit all the basic blocks in lexicographical order. Dominator traversals are also possible using `walk_dominator_tree'. Given two basic blocks A and B, block A dominates block B if A is _always_ executed before B. The `BASIC_BLOCK' array contains all basic blocks in an unspecified order. Each `basic_block' structure has a field that holds a unique integer identifier `index' that is the index of the block in the `BASIC_BLOCK' array. The total number of basic blocks in the function is `n_basic_blocks'. Both the basic block indices and the total number of basic blocks may vary during the compilation process, as passes reorder, create, duplicate, and destroy basic blocks. The index for any block should never be greater than `last_basic_block'. Special basic blocks represent possible entry and exit points of a function. These blocks are called `ENTRY_BLOCK_PTR' and `EXIT_BLOCK_PTR'. These blocks do not contain any code, and are not elements of the `BASIC_BLOCK' array. Therefore they have been assigned unique, negative index numbers. Each `basic_block' also contains pointers to the first instruction (the "head") and the last instruction (the "tail") or "end" of the instruction stream contained in a basic block. In fact, since the `basic_block' data type is used to represent blocks in both major intermediate representations of GCC (`tree' and RTL), there are pointers to the head and end of a basic block for both representations. For RTL, these pointers are `rtx head, end'. In the RTL function representation, the head pointer always points either to a `NOTE_INSN_BASIC_BLOCK' or to a `CODE_LABEL', if present. In the RTL representation of a function, the instruction stream contains not only the "real" instructions, but also "notes". Any function that moves or duplicates the basic blocks needs to take care of updating of these notes. Many of these notes expect that the instruction stream consists of linear regions, making such updates difficult. The `NOTE_INSN_BASIC_BLOCK' note is the only kind of note that may appear in the instruction stream contained in a basic block. The instruction stream of a basic block always follows a `NOTE_INSN_BASIC_BLOCK', but zero or more `CODE_LABEL' nodes can precede the block note. A basic block ends by control flow instruction or last instruction before following `CODE_LABEL' or `NOTE_INSN_BASIC_BLOCK'. A `CODE_LABEL' cannot appear in the instruction stream of a basic block. In addition to notes, the jump table vectors are also represented as "pseudo-instructions" inside the insn stream. These vectors never appear in the basic block and should always be placed just after the table jump instructions referencing them. After removing the table-jump it is often difficult to eliminate the code computing the address and referencing the vector, so cleaning up these vectors is postponed until after liveness analysis. Thus the jump table vectors may appear in the insn stream unreferenced and without any purpose. Before any edge is made "fall-thru", the existence of such construct in the way needs to be checked by calling `can_fallthru' function. For the `tree' representation, the head and end of the basic block are being pointed to by the `stmt_list' field, but this special `tree' should never be referenced directly. Instead, at the tree level abstract containers and iterators are used to access statements and expressions in basic blocks. These iterators are called "block statement iterators" (BSIs). Grep for `^bsi' in the various `tree-*' files. The following snippet will pretty-print all the statements of the program in the GIMPLE representation. FOR_EACH_BB (bb) { block_stmt_iterator si; for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) { tree stmt = bsi_stmt (si); print_generic_stmt (stderr, stmt, 0); } }  File: gccint.info, Node: Edges, Next: Profile information, Prev: Basic Blocks, Up: Control Flow 13.2 Edges ========== Edges represent possible control flow transfers from the end of some basic block A to the head of another basic block B. We say that A is a predecessor of B, and B is a successor of A. Edges are represented in GCC with the `edge' data type. Each `edge' acts as a link between two basic blocks: the `src' member of an edge points to the predecessor basic block of the `dest' basic block. The members `preds' and `succs' of the `basic_block' data type point to type-safe vectors of edges to the predecessors and successors of the block. When walking the edges in an edge vector, "edge iterators" should be used. Edge iterators are constructed using the `edge_iterator' data structure and several methods are available to operate on them: `ei_start' This function initializes an `edge_iterator' that points to the first edge in a vector of edges. `ei_last' This function initializes an `edge_iterator' that points to the last edge in a vector of edges. `ei_end_p' This predicate is `true' if an `edge_iterator' represents the last edge in an edge vector. `ei_one_before_end_p' This predicate is `true' if an `edge_iterator' represents the second last edge in an edge vector. `ei_next' This function takes a pointer to an `edge_iterator' and makes it point to the next edge in the sequence. `ei_prev' This function takes a pointer to an `edge_iterator' and makes it point to the previous edge in the sequence. `ei_edge' This function returns the `edge' currently pointed to by an `edge_iterator'. `ei_safe_safe' This function returns the `edge' currently pointed to by an `edge_iterator', but returns `NULL' if the iterator is pointing at the end of the sequence. This function has been provided for existing code makes the assumption that a `NULL' edge indicates the end of the sequence. The convenience macro `FOR_EACH_EDGE' can be used to visit all of the edges in a sequence of predecessor or successor edges. It must not be used when an element might be removed during the traversal, otherwise elements will be missed. Here is an example of how to use the macro: edge e; edge_iterator ei; FOR_EACH_EDGE (e, ei, bb->succs) { if (e->flags & EDGE_FALLTHRU) break; } There are various reasons why control flow may transfer from one block to another. One possibility is that some instruction, for example a `CODE_LABEL', in a linearized instruction stream just always starts a new basic block. In this case a "fall-thru" edge links the basic block to the first following basic block. But there are several other reasons why edges may be created. The `flags' field of the `edge' data type is used to store information about the type of edge we are dealing with. Each edge is of one of the following types: _jump_ No type flags are set for edges corresponding to jump instructions. These edges are used for unconditional or conditional jumps and in RTL also for table jumps. They are the easiest to manipulate as they may be freely redirected when the flow graph is not in SSA form. _fall-thru_ Fall-thru edges are present in case where the basic block may continue execution to the following one without branching. These edges have the `EDGE_FALLTHRU' flag set. Unlike other types of edges, these edges must come into the basic block immediately following in the instruction stream. The function `force_nonfallthru' is available to insert an unconditional jump in the case that redirection is needed. Note that this may require creation of a new basic block. _exception handling_ Exception handling edges represent possible control transfers from a trapping instruction to an exception handler. The definition of "trapping" varies. In C++, only function calls can throw, but for Java, exceptions like division by zero or segmentation fault are defined and thus each instruction possibly throwing this kind of exception needs to be handled as control flow instruction. Exception edges have the `EDGE_ABNORMAL' and `EDGE_EH' flags set. When updating the instruction stream it is easy to change possibly trapping instruction to non-trapping, by simply removing the exception edge. The opposite conversion is difficult, but should not happen anyway. The edges can be eliminated via `purge_dead_edges' call. In the RTL representation, the destination of an exception edge is specified by `REG_EH_REGION' note attached to the insn. In case of a trapping call the `EDGE_ABNORMAL_CALL' flag is set too. In the `tree' representation, this extra flag is not set. In the RTL representation, the predicate `may_trap_p' may be used to check whether instruction still may trap or not. For the tree representation, the `tree_could_trap_p' predicate is available, but this predicate only checks for possible memory traps, as in dereferencing an invalid pointer location. _sibling calls_ Sibling calls or tail calls terminate the function in a non-standard way and thus an edge to the exit must be present. `EDGE_SIBCALL' and `EDGE_ABNORMAL' are set in such case. These edges only exist in the RTL representation. _computed jumps_ Computed jumps contain edges to all labels in the function referenced from the code. All those edges have `EDGE_ABNORMAL' flag set. The edges used to represent computed jumps often cause compile time performance problems, since functions consisting of many taken labels and many computed jumps may have _very_ dense flow graphs, so these edges need to be handled with special care. During the earlier stages of the compilation process, GCC tries to avoid such dense flow graphs by factoring computed jumps. For example, given the following series of jumps, goto *x; [ ... ] goto *x; [ ... ] goto *x; [ ... ] factoring the computed jumps results in the following code sequence which has a much simpler flow graph: goto y; [ ... ] goto y; [ ... ] goto y; [ ... ] y: goto *x; However, the classic problem with this transformation is that it has a runtime cost in there resulting code: An extra jump. Therefore, the computed jumps are un-factored in the later passes of the compiler. Be aware of that when you work on passes in that area. There have been numerous examples already where the compile time for code with unfactored computed jumps caused some serious headaches. _nonlocal goto handlers_ GCC allows nested functions to return into caller using a `goto' to a label passed to as an argument to the callee. The labels passed to nested functions contain special code to cleanup after function call. Such sections of code are referred to as "nonlocal goto receivers". If a function contains such nonlocal goto receivers, an edge from the call to the label is created with the `EDGE_ABNORMAL' and `EDGE_ABNORMAL_CALL' flags set. _function entry points_ By definition, execution of function starts at basic block 0, so there is always an edge from the `ENTRY_BLOCK_PTR' to basic block 0. There is no `tree' representation for alternate entry points at this moment. In RTL, alternate entry points are specified by `CODE_LABEL' with `LABEL_ALTERNATE_NAME' defined. This feature is currently used for multiple entry point prologues and is limited to post-reload passes only. This can be used by back-ends to emit alternate prologues for functions called from different contexts. In future full support for multiple entry functions defined by Fortran 90 needs to be implemented. _function exits_ In the pre-reload representation a function terminates after the last instruction in the insn chain and no explicit return instructions are used. This corresponds to the fall-thru edge into exit block. After reload, optimal RTL epilogues are used that use explicit (conditional) return instructions that are represented by edges with no flags set.  File: gccint.info, Node: Profile information, Next: Maintaining the CFG, Prev: Edges, Up: Control Flow 13.3 Profile information ======================== In many cases a compiler must make a choice whether to trade speed in one part of code for speed in another, or to trade code size for code speed. In such cases it is useful to know information about how often some given block will be executed. That is the purpose for maintaining profile within the flow graph. GCC can handle profile information obtained through "profile feedback", but it can also estimate branch probabilities based on statics and heuristics. The feedback based profile is produced by compiling the program with instrumentation, executing it on a train run and reading the numbers of executions of basic blocks and edges back to the compiler while re-compiling the program to produce the final executable. This method provides very accurate information about where a program spends most of its time on the train run. Whether it matches the average run of course depends on the choice of train data set, but several studies have shown that the behavior of a program usually changes just marginally over different data sets. When profile feedback is not available, the compiler may be asked to attempt to predict the behavior of each branch in the program using a set of heuristics (see `predict.def' for details) and compute estimated frequencies of each basic block by propagating the probabilities over the graph. Each `basic_block' contains two integer fields to represent profile information: `frequency' and `count'. The `frequency' is an estimation how often is basic block executed within a function. It is represented as an integer scaled in the range from 0 to `BB_FREQ_BASE'. The most frequently executed basic block in function is initially set to `BB_FREQ_BASE' and the rest of frequencies are scaled accordingly. During optimization, the frequency of the most frequent basic block can both decrease (for instance by loop unrolling) or grow (for instance by cross-jumping optimization), so scaling sometimes has to be performed multiple times. The `count' contains hard-counted numbers of execution measured during training runs and is nonzero only when profile feedback is available. This value is represented as the host's widest integer (typically a 64 bit integer) of the special type `gcov_type'. Most optimization passes can use only the frequency information of a basic block, but a few passes may want to know hard execution counts. The frequencies should always match the counts after scaling, however during updating of the profile information numerical error may accumulate into quite large errors. Each edge also contains a branch probability field: an integer in the range from 0 to `REG_BR_PROB_BASE'. It represents probability of passing control from the end of the `src' basic block to the `dest' basic block, i.e. the probability that control will flow along this edge. The `EDGE_FREQUENCY' macro is available to compute how frequently a given edge is taken. There is a `count' field for each edge as well, representing same information as for a basic block. The basic block frequencies are not represented in the instruction stream, but in the RTL representation the edge frequencies are represented for conditional jumps (via the `REG_BR_PROB' macro) since they are used when instructions are output to the assembly file and the flow graph is no longer maintained. The probability that control flow arrives via a given edge to its destination basic block is called "reverse probability" and is not directly represented, but it may be easily computed from frequencies of basic blocks. Updating profile information is a delicate task that can unfortunately not be easily integrated with the CFG manipulation API. Many of the functions and hooks to modify the CFG, such as `redirect_edge_and_branch', do not have enough information to easily update the profile,