This is ../../gcc-3.4/gcc/doc/gccint.info, produced by makeinfo version
4.2 from ../../gcc-3.4/gcc/doc/gccint.texi.

Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.

   Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.2 or
any later version published by the Free Software Foundation; with the
Invariant Sections being "GNU General Public License" and "Funding Free
Software", the Front-Cover texts being (a) (see below), and with the
Back-Cover Texts being (b) (see below).  A copy of the license is
included in the section entitled "GNU Free Documentation License".

   (a) The FSF's Front-Cover Text is:

   A GNU Manual

   (b) The FSF's Back-Cover Text is:

   You have freedom to copy and modify this GNU Manual, like GNU
software.  Copies published by the Free Software Foundation raise
funds for GNU development.
INFO-DIR-SECTION Programming
START-INFO-DIR-ENTRY
* gccint: (gccint).            Internals of the GNU Compiler Collection.
END-INFO-DIR-ENTRY
   This file documents the internals of the GNU compilers.

   Published by the Free Software Foundation
59 Temple Place - Suite 330
Boston, MA 02111-1307 USA

File: gccint.info,  Node: Defining Attributes,  Next: Expressions,  Up: Insn Attributes

Defining Attributes and their Values
------------------------------------

   The `define_attr' expression is used to define each attribute
required by the target machine.  It looks like:

     (define_attr NAME LIST-OF-VALUES DEFAULT)

   NAME is a string specifying the name of the attribute being defined.

   LIST-OF-VALUES is either a string that specifies a comma-separated
list of values that can be assigned to the attribute, or a null string
to indicate that the attribute takes numeric values.

   DEFAULT is an attribute expression that gives the value of this
attribute for insns that match patterns whose definition does not
include an explicit value for this attribute.  *Note Attr Example::,
for more information on the handling of defaults.  *Note Constant
Attributes::, for information on attributes that do not depend on any
particular insn.

   For each defined attribute, a number of definitions are written to
the `insn-attr.h' file.  For cases where an explicit set of values is
specified for an attribute, the following are defined:

   * A `#define' is written for the symbol `HAVE_ATTR_NAME'.

   * An enumeral class is defined for `attr_NAME' with elements of the
     form `UPPER-NAME_UPPER-VALUE' where the attribute name and value
     are first converted to uppercase.

   * A function `get_attr_NAME' is defined that is passed an insn and
     returns the attribute value for that insn.

   For example, if the following is present in the `md' file:

     (define_attr "type" "branch,fp,load,store,arith" ...)

the following lines will be written to the file `insn-attr.h'.

     #define HAVE_ATTR_type
     enum attr_type {TYPE_BRANCH, TYPE_FP, TYPE_LOAD,
                      TYPE_STORE, TYPE_ARITH};
     extern enum attr_type get_attr_type ();

   If the attribute takes numeric values, no `enum' type will be
defined and the function to obtain the attribute's value will return
`int'.


File: gccint.info,  Node: Expressions,  Next: Tagging Insns,  Prev: Defining Attributes,  Up: Insn Attributes

Attribute Expressions
---------------------

   RTL expressions used to define attributes use the codes described
above plus a few specific to attribute definitions, to be discussed
below.  Attribute value expressions must have one of the following
forms:

`(const_int I)'
     The integer I specifies the value of a numeric attribute.  I must
     be non-negative.

     The value of a numeric attribute can be specified either with a
     `const_int', or as an integer represented as a string in
     `const_string', `eq_attr' (see below), `attr', `symbol_ref',
     simple arithmetic expressions, and `set_attr' overrides on
     specific instructions (*note Tagging Insns::).

`(const_string VALUE)'
     The string VALUE specifies a constant attribute value.  If VALUE
     is specified as `"*"', it means that the default value of the
     attribute is to be used for the insn containing this expression.
     `"*"' obviously cannot be used in the DEFAULT expression of a
     `define_attr'.

     If the attribute whose value is being specified is numeric, VALUE
     must be a string containing a non-negative integer (normally
     `const_int' would be used in this case).  Otherwise, it must
     contain one of the valid values for the attribute.

`(if_then_else TEST TRUE-VALUE FALSE-VALUE)'
     TEST specifies an attribute test, whose format is defined below.
     The value of this expression is TRUE-VALUE if TEST is true,
     otherwise it is FALSE-VALUE.

`(cond [TEST1 VALUE1 ...] DEFAULT)'
     The first operand of this expression is a vector containing an even
     number of expressions and consisting of pairs of TEST and VALUE
     expressions.  The value of the `cond' expression is that of the
     VALUE corresponding to the first true TEST expression.  If none of
     the TEST expressions are true, the value of the `cond' expression
     is that of the DEFAULT expression.

   TEST expressions can have one of the following forms:

`(const_int I)'
     This test is true if I is nonzero and false otherwise.

`(not TEST)'
`(ior TEST1 TEST2)'
`(and TEST1 TEST2)'
     These tests are true if the indicated logical function is true.

`(match_operand:M N PRED CONSTRAINTS)'
     This test is true if operand N of the insn whose attribute value
     is being determined has mode M (this part of the test is ignored
     if M is `VOIDmode') and the function specified by the string PRED
     returns a nonzero value when passed operand N and mode M (this
     part of the test is ignored if PRED is the null string).

     The CONSTRAINTS operand is ignored and should be the null string.

`(le ARITH1 ARITH2)'
`(leu ARITH1 ARITH2)'
`(lt ARITH1 ARITH2)'
`(ltu ARITH1 ARITH2)'
`(gt ARITH1 ARITH2)'
`(gtu ARITH1 ARITH2)'
`(ge ARITH1 ARITH2)'
`(geu ARITH1 ARITH2)'
`(ne ARITH1 ARITH2)'
`(eq ARITH1 ARITH2)'
     These tests are true if the indicated comparison of the two
     arithmetic expressions is true.  Arithmetic expressions are formed
     with `plus', `minus', `mult', `div', `mod', `abs', `neg', `and',
     `ior', `xor', `not', `ashift', `lshiftrt', and `ashiftrt'
     expressions.

     `const_int' and `symbol_ref' are always valid terms (*note Insn
     Lengths::,for additional forms).  `symbol_ref' is a string
     denoting a C expression that yields an `int' when evaluated by the
     `get_attr_...' routine.  It should normally be a global variable.

`(eq_attr NAME VALUE)'
     NAME is a string specifying the name of an attribute.

     VALUE is a string that is either a valid value for attribute NAME,
     a comma-separated list of values, or `!' followed by a value or
     list.  If VALUE does not begin with a `!', this test is true if
     the value of the NAME attribute of the current insn is in the list
     specified by VALUE.  If VALUE begins with a `!', this test is true
     if the attribute's value is _not_ in the specified list.

     For example,

          (eq_attr "type" "load,store")

     is equivalent to

          (ior (eq_attr "type" "load") (eq_attr "type" "store"))

     If NAME specifies an attribute of `alternative', it refers to the
     value of the compiler variable `which_alternative' (*note Output
     Statement::) and the values must be small integers.  For example,

          (eq_attr "alternative" "2,3")

     is equivalent to

          (ior (eq (symbol_ref "which_alternative") (const_int 2))
               (eq (symbol_ref "which_alternative") (const_int 3)))

     Note that, for most attributes, an `eq_attr' test is simplified in
     cases where the value of the attribute being tested is known for
     all insns matching a particular pattern.  This is by far the most
     common case.

`(attr_flag NAME)'
     The value of an `attr_flag' expression is true if the flag
     specified by NAME is true for the `insn' currently being scheduled.

     NAME is a string specifying one of a fixed set of flags to test.
     Test the flags `forward' and `backward' to determine the direction
     of a conditional branch.  Test the flags `very_likely', `likely',
     `very_unlikely', and `unlikely' to determine if a conditional
     branch is expected to be taken.

     If the `very_likely' flag is true, then the `likely' flag is also
     true.  Likewise for the `very_unlikely' and `unlikely' flags.

     This example describes a conditional branch delay slot which can
     be nullified for forward branches that are taken (annul-true) or
     for backward branches which are not taken (annul-false).

          (define_delay (eq_attr "type" "cbranch")
            [(eq_attr "in_branch_delay" "true")
             (and (eq_attr "in_branch_delay" "true")
                  (attr_flag "forward"))
             (and (eq_attr "in_branch_delay" "true")
                  (attr_flag "backward"))])

     The `forward' and `backward' flags are false if the current `insn'
     being scheduled is not a conditional branch.

     The `very_likely' and `likely' flags are true if the `insn' being
     scheduled is not a conditional branch.  The `very_unlikely' and
     `unlikely' flags are false if the `insn' being scheduled is not a
     conditional branch.

     `attr_flag' is only used during delay slot scheduling and has no
     meaning to other passes of the compiler.

`(attr NAME)'
     The value of another attribute is returned.  This is most useful
     for numeric attributes, as `eq_attr' and `attr_flag' produce more
     efficient code for non-numeric attributes.


File: gccint.info,  Node: Tagging Insns,  Next: Attr Example,  Prev: Expressions,  Up: Insn Attributes

Assigning Attribute Values to Insns
-----------------------------------

   The value assigned to an attribute of an insn is primarily
determined by which pattern is matched by that insn (or which
`define_peephole' generated it).  Every `define_insn' and
`define_peephole' can have an optional last argument to specify the
values of attributes for matching insns.  The value of any attribute
not specified in a particular insn is set to the default value for that
attribute, as specified in its `define_attr'.  Extensive use of default
values for attributes permits the specification of the values for only
one or two attributes in the definition of most insn patterns, as seen
in the example in the next section.

   The optional last argument of `define_insn' and `define_peephole' is
a vector of expressions, each of which defines the value for a single
attribute.  The most general way of assigning an attribute's value is
to use a `set' expression whose first operand is an `attr' expression
giving the name of the attribute being set.  The second operand of the
`set' is an attribute expression (*note Expressions::) giving the value
of the attribute.

   When the attribute value depends on the `alternative' attribute
(i.e., which is the applicable alternative in the constraint of the
insn), the `set_attr_alternative' expression can be used.  It allows
the specification of a vector of attribute expressions, one for each
alternative.

   When the generality of arbitrary attribute expressions is not
required, the simpler `set_attr' expression can be used, which allows
specifying a string giving either a single attribute value or a list of
attribute values, one for each alternative.

   The form of each of the above specifications is shown below.  In
each case, NAME is a string specifying the attribute to be set.

`(set_attr NAME VALUE-STRING)'
     VALUE-STRING is either a string giving the desired attribute value,
     or a string containing a comma-separated list giving the values for
     succeeding alternatives.  The number of elements must match the
     number of alternatives in the constraint of the insn pattern.

     Note that it may be useful to specify `*' for some alternative, in
     which case the attribute will assume its default value for insns
     matching that alternative.

`(set_attr_alternative NAME [VALUE1 VALUE2 ...])'
     Depending on the alternative of the insn, the value will be one of
     the specified values.  This is a shorthand for using a `cond' with
     tests on the `alternative' attribute.

`(set (attr NAME) VALUE)'
     The first operand of this `set' must be the special RTL expression
     `attr', whose sole operand is a string giving the name of the
     attribute being set.  VALUE is the value of the attribute.

   The following shows three different ways of representing the same
attribute value specification:

     (set_attr "type" "load,store,arith")
     
     (set_attr_alternative "type"
                           [(const_string "load") (const_string "store")
                            (const_string "arith")])
     
     (set (attr "type")
          (cond [(eq_attr "alternative" "1") (const_string "load")
                 (eq_attr "alternative" "2") (const_string "store")]
                (const_string "arith")))

   The `define_asm_attributes' expression provides a mechanism to
specify the attributes assigned to insns produced from an `asm'
statement.  It has the form:

     (define_asm_attributes [ATTR-SETS])

where ATTR-SETS is specified the same as for both the `define_insn' and
the `define_peephole' expressions.

   These values will typically be the "worst case" attribute values.
For example, they might indicate that the condition code will be
clobbered.

   A specification for a `length' attribute is handled specially.  The
way to compute the length of an `asm' insn is to multiply the length
specified in the expression `define_asm_attributes' by the number of
machine instructions specified in the `asm' statement, determined by
counting the number of semicolons and newlines in the string.
Therefore, the value of the `length' attribute specified in a
`define_asm_attributes' should be the maximum possible length of a
single machine instruction.


File: gccint.info,  Node: Attr Example,  Next: Insn Lengths,  Prev: Tagging Insns,  Up: Insn Attributes

Example of Attribute Specifications
-----------------------------------

   The judicious use of defaulting is important in the efficient use of
insn attributes.  Typically, insns are divided into "types" and an
attribute, customarily called `type', is used to represent this value.
This attribute is normally used only to define the default value for
other attributes.  An example will clarify this usage.

   Assume we have a RISC machine with a condition code and in which only
full-word operations are performed in registers.  Let us assume that we
can divide all insns into loads, stores, (integer) arithmetic
operations, floating point operations, and branches.

   Here we will concern ourselves with determining the effect of an
insn on the condition code and will limit ourselves to the following
possible effects:  The condition code can be set unpredictably
(clobbered), not be changed, be set to agree with the results of the
operation, or only changed if the item previously set into the
condition code has been modified.

   Here is part of a sample `md' file for such a machine:

     (define_attr "type" "load,store,arith,fp,branch" (const_string "arith"))
     
     (define_attr "cc" "clobber,unchanged,set,change0"
                  (cond [(eq_attr "type" "load")
                             (const_string "change0")
                         (eq_attr "type" "store,branch")
                             (const_string "unchanged")
                         (eq_attr "type" "arith")
                             (if_then_else (match_operand:SI 0 "" "")
                                           (const_string "set")
                                           (const_string "clobber"))]
                        (const_string "clobber")))
     
     (define_insn ""
       [(set (match_operand:SI 0 "general_operand" "=r,r,m")
             (match_operand:SI 1 "general_operand" "r,m,r"))]
       ""
       "@
        move %0,%1
        load %0,%1
        store %0,%1"
       [(set_attr "type" "arith,load,store")])

   Note that we assume in the above example that arithmetic operations
performed on quantities smaller than a machine word clobber the
condition code since they will set the condition code to a value
corresponding to the full-word result.


File: gccint.info,  Node: Insn Lengths,  Next: Constant Attributes,  Prev: Attr Example,  Up: Insn Attributes

Computing the Length of an Insn
-------------------------------

   For many machines, multiple types of branch instructions are
provided, each for different length branch displacements.  In most
cases, the assembler will choose the correct instruction to use.
However, when the assembler cannot do so, GCC can when a special
attribute, the `length' attribute, is defined.  This attribute must be
defined to have numeric values by specifying a null string in its
`define_attr'.

   In the case of the `length' attribute, two additional forms of
arithmetic terms are allowed in test expressions:

`(match_dup N)'
     This refers to the address of operand N of the current insn, which
     must be a `label_ref'.

`(pc)'
     This refers to the address of the _current_ insn.  It might have
     been more consistent with other usage to make this the address of
     the _next_ insn but this would be confusing because the length of
     the current insn is to be computed.

   For normal insns, the length will be determined by value of the
`length' attribute.  In the case of `addr_vec' and `addr_diff_vec' insn
patterns, the length is computed as the number of vectors multiplied by
the size of each vector.

   Lengths are measured in addressable storage units (bytes).

   The following macros can be used to refine the length computation:

`FIRST_INSN_ADDRESS'
     When the `length' insn attribute is used, this macro specifies the
     value to be assigned to the address of the first insn in a
     function.  If not specified, 0 is used.

`ADJUST_INSN_LENGTH (INSN, LENGTH)'
     If defined, modifies the length assigned to instruction INSN as a
     function of the context in which it is used.  LENGTH is an lvalue
     that contains the initially computed length of the insn and should
     be updated with the correct length of the insn.

     This macro will normally not be required.  A case in which it is
     required is the ROMP.  On this machine, the size of an `addr_vec'
     insn must be increased by two to compensate for the fact that
     alignment may be required.

   The routine that returns `get_attr_length' (the value of the
`length' attribute) can be used by the output routine to determine the
form of the branch instruction to be written, as the example below
illustrates.

   As an example of the specification of variable-length branches,
consider the IBM 360.  If we adopt the convention that a register will
be set to the starting address of a function, we can jump to labels
within 4k of the start using a four-byte instruction.  Otherwise, we
need a six-byte sequence to load the address from memory and then
branch to it.

   On such a machine, a pattern for a branch instruction might be
specified as follows:

     (define_insn "jump"
       [(set (pc)
             (label_ref (match_operand 0 "" "")))]
       ""
     {
        return (get_attr_length (insn) == 4
                ? "b %l0" : "l r15,=a(%l0); br r15");
     }
       [(set (attr "length")
             (if_then_else (lt (match_dup 0) (const_int 4096))
                           (const_int 4)
                           (const_int 6)))])


File: gccint.info,  Node: Constant Attributes,  Next: Delay Slots,  Prev: Insn Lengths,  Up: Insn Attributes

Constant Attributes
-------------------

   A special form of `define_attr', where the expression for the
default value is a `const' expression, indicates an attribute that is
constant for a given run of the compiler.  Constant attributes may be
used to specify which variety of processor is used.  For example,

     (define_attr "cpu" "m88100,m88110,m88000"
      (const
       (cond [(symbol_ref "TARGET_88100") (const_string "m88100")
              (symbol_ref "TARGET_88110") (const_string "m88110")]
             (const_string "m88000"))))
     
     (define_attr "memory" "fast,slow"
      (const
       (if_then_else (symbol_ref "TARGET_FAST_MEM")
                     (const_string "fast")
                     (const_string "slow"))))

   The routine generated for constant attributes has no parameters as it
does not depend on any particular insn.  RTL expressions used to define
the value of a constant attribute may use the `symbol_ref' form, but
may not use either the `match_operand' form or `eq_attr' forms
involving insn attributes.


File: gccint.info,  Node: Delay Slots,  Next: Processor pipeline description,  Prev: Constant Attributes,  Up: Insn Attributes

Delay Slot Scheduling
---------------------

   The insn attribute mechanism can be used to specify the requirements
for delay slots, if any, on a target machine.  An instruction is said to
require a "delay slot" if some instructions that are physically after
the instruction are executed as if they were located before it.
Classic examples are branch and call instructions, which often execute
the following instruction before the branch or call is performed.

   On some machines, conditional branch instructions can optionally
"annul" instructions in the delay slot.  This means that the
instruction will not be executed for certain branch outcomes.  Both
instructions that annul if the branch is true and instructions that
annul if the branch is false are supported.

   Delay slot scheduling differs from instruction scheduling in that
determining whether an instruction needs a delay slot is dependent only
on the type of instruction being generated, not on data flow between the
instructions.  See the next section for a discussion of data-dependent
instruction scheduling.

   The requirement of an insn needing one or more delay slots is
indicated via the `define_delay' expression.  It has the following form:

     (define_delay TEST
                   [DELAY-1 ANNUL-TRUE-1 ANNUL-FALSE-1
                    DELAY-2 ANNUL-TRUE-2 ANNUL-FALSE-2
                    ...])

   TEST is an attribute test that indicates whether this `define_delay'
applies to a particular insn.  If so, the number of required delay
slots is determined by the length of the vector specified as the second
argument.  An insn placed in delay slot N must satisfy attribute test
DELAY-N.  ANNUL-TRUE-N is an attribute test that specifies which insns
may be annulled if the branch is true.  Similarly, ANNUL-FALSE-N
specifies which insns in the delay slot may be annulled if the branch
is false.  If annulling is not supported for that delay slot, `(nil)'
should be coded.

   For example, in the common case where branch and call insns require
a single delay slot, which may contain any insn other than a branch or
call, the following would be placed in the `md' file:

     (define_delay (eq_attr "type" "branch,call")
                   [(eq_attr "type" "!branch,call") (nil) (nil)])

   Multiple `define_delay' expressions may be specified.  In this case,
each such expression specifies different delay slot requirements and
there must be no insn for which tests in two `define_delay' expressions
are both true.

   For example, if we have a machine that requires one delay slot for
branches but two for calls,  no delay slot can contain a branch or call
insn, and any valid insn in the delay slot for the branch can be
annulled if the branch is true, we might represent this as follows:

     (define_delay (eq_attr "type" "branch")
        [(eq_attr "type" "!branch,call")
         (eq_attr "type" "!branch,call")
         (nil)])
     
     (define_delay (eq_attr "type" "call")
                   [(eq_attr "type" "!branch,call") (nil) (nil)
                    (eq_attr "type" "!branch,call") (nil) (nil)])


File: gccint.info,  Node: Processor pipeline description,  Prev: Delay Slots,  Up: Insn Attributes

Specifying processor pipeline description
-----------------------------------------

   To achieve better performance, most modern processors
(super-pipelined, superscalar RISC, and VLIW processors) have many
"functional units" on which several instructions can be executed
simultaneously.  An instruction starts execution if its issue
conditions are satisfied.  If not, the instruction is stalled until its
conditions are satisfied.  Such "interlock (pipeline) delay" causes
interruption of the fetching of successor instructions (or demands nop
instructions, e.g. for some MIPS processors).

   There are two major kinds of interlock delays in modern processors.
The first one is a data dependence delay determining "instruction
latency time".  The instruction execution is not started until all
source data have been evaluated by prior instructions (there are more
complex cases when the instruction execution starts even when the data
are not available but will be ready in given time after the instruction
execution start).  Taking the data dependence delays into account is
simple.  The data dependence (true, output, and anti-dependence) delay
between two instructions is given by a constant.  In most cases this
approach is adequate.  The second kind of interlock delays is a
reservation delay.  The reservation delay means that two instructions
under execution will be in need of shared processors resources, i.e.
buses, internal registers, and/or functional units, which are reserved
for some time.  Taking this kind of delay into account is complex
especially for modern RISC processors.

   The task of exploiting more processor parallelism is solved by an
instruction scheduler.  For a better solution to this problem, the
instruction scheduler has to have an adequate description of the
processor parallelism (or "pipeline description").  Currently GCC
provides two alternative ways to describe processor parallelism, both
described below.  The first method is outlined in the next section; it
was once the only method provided by GCC, and thus is used in a number
of exiting ports.  The second, and preferred method, specifies
functional unit reservations for groups of instructions with the aid of
"regular expressions".  This is called the "automaton based
description".

   The GCC instruction scheduler uses a "pipeline hazard recognizer" to
figure out the possibility of the instruction issue by the processor on
a given simulated processor cycle.  The pipeline hazard recognizer is
automatically generated from the processor pipeline description.  The
pipeline hazard recognizer generated from the automaton based
description is more sophisticated and based on a deterministic finite
state automaton (DFA) and therefore faster than one generated from the
old description.  Furthermore, its speed is not dependent on processor
complexity.  The instruction issue is possible if there is a transition
from one automaton state to another one.

   You can use either model to describe processor pipeline
characteristics or even mix them.  You could use the old description
for some processor submodels and the DFA-based one for other processor
submodels.

   In general, using the automaton based description is preferred.  Its
model is richer and makes it possible to more accurately describe
pipeline characteristics of processors, which results in improved code
quality (although sometimes only marginally).  It will also be used as
an infrastructure to implement sophisticated and practical instruction
scheduling which will try many instruction sequences to choose the best
one.

* Menu:

* Old pipeline description:: Specifying information for insn scheduling.
* Automaton pipeline description:: Describing insn pipeline characteristics.
* Comparison of the two descriptions:: Drawbacks of the old pipeline description


File: gccint.info,  Node: Old pipeline description,  Next: Automaton pipeline description,  Up: Processor pipeline description

Specifying Function Units
.........................

   On most RISC machines, there are instructions whose results are not
available for a specific number of cycles.  Common cases are
instructions that load data from memory.  On many machines, a pipeline
stall will result if the data is referenced too soon after the load
instruction.

   In addition, many newer microprocessors have multiple function
units, usually one for integer and one for floating point, and often
will incur pipeline stalls when a result that is needed is not yet
ready.

   The descriptions in this section allow the specification of how much
time must elapse between the execution of an instruction and the time
when its result is used.  It also allows specification of when the
execution of an instruction will delay execution of similar instructions
due to function unit conflicts.

   For the purposes of the specifications in this section, a machine is
divided into "function units", each of which execute a specific class
of instructions in first-in-first-out order.  Function units that
accept one instruction each cycle and allow a result to be used in the
succeeding instruction (usually via forwarding) need not be specified.
Classic RISC microprocessors will normally have a single function unit,
which we can call `memory'.  The newer "superscalar" processors will
often have function units for floating point operations, usually at
least a floating point adder and multiplier.

   Each usage of a function units by a class of insns is specified with
a `define_function_unit' expression, which looks like this:

     (define_function_unit NAME MULTIPLICITY SIMULTANEITY
                           TEST READY-DELAY ISSUE-DELAY
                          [CONFLICT-LIST])

   NAME is a string giving the name of the function unit.

   MULTIPLICITY is an integer specifying the number of identical units
in the processor.  If more than one unit is specified, they will be
scheduled independently.  Only truly independent units should be
counted; a pipelined unit should be specified as a single unit.  (The
only common example of a machine that has multiple function units for a
single instruction class that are truly independent and not pipelined
are the two multiply and two increment units of the CDC 6600.)

   SIMULTANEITY specifies the maximum number of insns that can be
executing in each instance of the function unit simultaneously or zero
if the unit is pipelined and has no limit.

   All `define_function_unit' definitions referring to function unit
NAME must have the same name and values for MULTIPLICITY and
SIMULTANEITY.

   TEST is an attribute test that selects the insns we are describing
in this definition.  Note that an insn may use more than one function
unit and a function unit may be specified in more than one
`define_function_unit'.

   READY-DELAY is an integer that specifies the number of cycles after
which the result of the instruction can be used without introducing any
stalls.

   ISSUE-DELAY is an integer that specifies the number of cycles after
the instruction matching the TEST expression begins using this unit
until a subsequent instruction can begin.  A cost of N indicates an N-1
cycle delay.  A subsequent instruction may also be delayed if an
earlier instruction has a longer READY-DELAY value.  This blocking
effect is computed using the SIMULTANEITY, READY-DELAY, ISSUE-DELAY,
and CONFLICT-LIST terms.  For a normal non-pipelined function unit,
SIMULTANEITY is one, the unit is taken to block for the READY-DELAY
cycles of the executing insn, and smaller values of ISSUE-DELAY are
ignored.

   CONFLICT-LIST is an optional list giving detailed conflict costs for
this unit.  If specified, it is a list of condition test expressions to
be applied to insns chosen to execute in NAME following the particular
insn matching TEST that is already executing in NAME.  For each insn in
the list, ISSUE-DELAY specifies the conflict cost; for insns not in the
list, the cost is zero.  If not specified, CONFLICT-LIST defaults to
all instructions that use the function unit.

   Typical uses of this vector are where a floating point function unit
can pipeline either single- or double-precision operations, but not
both, or where a memory unit can pipeline loads, but not stores, etc.

   As an example, consider a classic RISC machine where the result of a
load instruction is not available for two cycles (a single "delay"
instruction is required) and where only one load instruction can be
executed simultaneously.  This would be specified as:

     (define_function_unit "memory" 1 1 (eq_attr "type" "load") 2 0)

   For the case of a floating point function unit that can pipeline
either single or double precision, but not both, the following could be
specified:

     (define_function_unit
        "fp" 1 0 (eq_attr "type" "sp_fp") 4 4 [(eq_attr "type" "dp_fp")])
     (define_function_unit
        "fp" 1 0 (eq_attr "type" "dp_fp") 4 4 [(eq_attr "type" "sp_fp")])

   *Note:* The scheduler attempts to avoid function unit conflicts and
uses all the specifications in the `define_function_unit' expression.
It has recently come to our attention that these specifications may not
allow modeling of some of the newer "superscalar" processors that have
insns using multiple pipelined units.  These insns will cause a
potential conflict for the second unit used during their execution and
there is no way of representing that conflict.  We welcome any examples
of how function unit conflicts work in such processors and suggestions
for their representation.


File: gccint.info,  Node: Automaton pipeline description,  Next: Comparison of the two descriptions,  Prev: Old pipeline description,  Up: Processor pipeline description

Describing instruction pipeline characteristics
...............................................

   This section describes constructions of the automaton based processor
pipeline description.  The order of constructions within the machine
description file is not important.

   The following optional construction describes names of automata
generated and used for the pipeline hazards recognition.  Sometimes the
generated finite state automaton used by the pipeline hazard recognizer
is large.  If we use more than one automaton and bind functional units
to the automata, the total size of the automata is usually less than
the size of the single automaton.  If there is no one such
construction, only one finite state automaton is generated.

     (define_automaton AUTOMATA-NAMES)

   AUTOMATA-NAMES is a string giving names of the automata.  The names
are separated by commas.  All the automata should have unique names.
The automaton name is used in the constructions `define_cpu_unit' and
`define_query_cpu_unit'.

   Each processor functional unit used in the description of instruction
reservations should be described by the following construction.

     (define_cpu_unit UNIT-NAMES [AUTOMATON-NAME])

   UNIT-NAMES is a string giving the names of the functional units
separated by commas.  Don't use name `nothing', it is reserved for
other goals.

   AUTOMATON-NAME is a string giving the name of the automaton with
which the unit is bound.  The automaton should be described in
construction `define_automaton'.  You should give "automaton-name", if
there is a defined automaton.

   The assignment of units to automata are constrained by the uses of
the units in insn reservations.  The most important constraint is: if a
unit reservation is present on a particular cycle of an alternative for
an insn reservation, then some unit from the same automaton must be
present on the same cycle for the other alternatives of the insn
reservation.  The rest of the constraints are mentioned in the
description of the subsequent constructions.

   The following construction describes CPU functional units analogously
to `define_cpu_unit'.  The reservation of such units can be queried for
an automaton state.  The instruction scheduler never queries
reservation of functional units for given automaton state.  So as a
rule, you don't need this construction.  This construction could be
used for future code generation goals (e.g. to generate VLIW insn
templates).

     (define_query_cpu_unit UNIT-NAMES [AUTOMATON-NAME])

   UNIT-NAMES is a string giving names of the functional units
separated by commas.

   AUTOMATON-NAME is a string giving the name of the automaton with
which the unit is bound.

   The following construction is the major one to describe pipeline
characteristics of an instruction.

     (define_insn_reservation INSN-NAME DEFAULT_LATENCY
                              CONDITION REGEXP)

   DEFAULT_LATENCY is a number giving latency time of the instruction.
There is an important difference between the old description and the
automaton based pipeline description.  The latency time is used for all
dependencies when we use the old description.  In the automaton based
pipeline description, the given latency time is only used for true
dependencies.  The cost of anti-dependencies is always zero and the
cost of output dependencies is the difference between latency times of
the producing and consuming insns (if the difference is negative, the
cost is considered to be zero).  You can always change the default
costs for any description by using the target hook
`TARGET_SCHED_ADJUST_COST' (*note Scheduling::).

   INSN-NAME is a string giving the internal name of the insn.  The
internal names are used in constructions `define_bypass' and in the
automaton description file generated for debugging.  The internal name
has nothing in common with the names in `define_insn'.  It is a good
practice to use insn classes described in the processor manual.

   CONDITION defines what RTL insns are described by this construction.
You should remember that you will be in trouble if CONDITION for two
or more different `define_insn_reservation' constructions is TRUE for
an insn.  In this case what reservation will be used for the insn is
not defined.  Such cases are not checked during generation of the
pipeline hazards recognizer because in general recognizing that two
conditions may have the same value is quite difficult (especially if
the conditions contain `symbol_ref').  It is also not checked during the
pipeline hazard recognizer work because it would slow down the
recognizer considerably.

   REGEXP is a string describing the reservation of the cpu's functional
units by the instruction.  The reservations are described by a regular
expression according to the following syntax:

            regexp = regexp "," oneof
                   | oneof
     
            oneof = oneof "|" allof
                  | allof
     
            allof = allof "+" repeat
                  | repeat
     
            repeat = element "*" number
                   | element
     
            element = cpu_function_unit_name
                    | reservation_name
                    | result_name
                    | "nothing"
                    | "(" regexp ")"

   * `,' is used for describing the start of the next cycle in the
     reservation.

   * `|' is used for describing a reservation described by the first
     regular expression *or* a reservation described by the second
     regular expression *or* etc.

   * `+' is used for describing a reservation described by the first
     regular expression *and* a reservation described by the second
     regular expression *and* etc.

   * `*' is used for convenience and simply means a sequence in which
     the regular expression are repeated NUMBER times with cycle
     advancing (see `,').

   * `cpu_function_unit_name' denotes reservation of the named
     functional unit.

   * `reservation_name' -- see description of construction
     `define_reservation'.

   * `nothing' denotes no unit reservations.

   Sometimes unit reservations for different insns contain common parts.
In such case, you can simplify the pipeline description by describing
the common part by the following construction

     (define_reservation RESERVATION-NAME REGEXP)

   RESERVATION-NAME is a string giving name of REGEXP.  Functional unit
names and reservation names are in the same name space.  So the
reservation names should be different from the functional unit names
and can not be the reserved name `nothing'.

   The following construction is used to describe exceptions in the
latency time for given instruction pair.  This is so called bypasses.

     (define_bypass NUMBER OUT_INSN_NAMES IN_INSN_NAMES
                    [GUARD])

   NUMBER defines when the result generated by the instructions given
in string OUT_INSN_NAMES will be ready for the instructions given in
string IN_INSN_NAMES.  The instructions in the string are separated by
commas.

   GUARD is an optional string giving the name of a C function which
defines an additional guard for the bypass.  The function will get the
two insns as parameters.  If the function returns zero the bypass will
be ignored for this case.  The additional guard is necessary to
recognize complicated bypasses, e.g. when the consumer is only an
address of insn `store' (not a stored value).

   The following five constructions are usually used to describe VLIW
processors, or more precisely, to describe a placement of small
instructions into VLIW instruction slots.  They can be used for RISC
processors, too.

     (exclusion_set UNIT-NAMES UNIT-NAMES)
     (presence_set UNIT-NAMES PATTERNS)
     (final_presence_set UNIT-NAMES PATTERNS)
     (absence_set UNIT-NAMES PATTERNS)
     (final_absence_set UNIT-NAMES PATTERNS)

   UNIT-NAMES is a string giving names of functional units separated by
commas.

   PATTERNS is a string giving patterns of functional units separated
by comma.  Currently pattern is is one unit or units separated by
white-spaces.

   The first construction (`exclusion_set') means that each functional
unit in the first string can not be reserved simultaneously with a unit
whose name is in the second string and vice versa.  For example, the
construction is useful for describing processors (e.g. some SPARC
processors) with a fully pipelined floating point functional unit which
can execute simultaneously only single floating point insns or only
double floating point insns.

   The second construction (`presence_set') means that each functional
unit in the first string can not be reserved unless at least one of
pattern of units whose names are in the second string is reserved.
This is an asymmetric relation.  For example, it is useful for
description that VLIW `slot1' is reserved after `slot0' reservation.
We could describe it by the following construction

     (presence_set "slot1" "slot0")

   Or `slot1' is reserved only after `slot0' and unit `b0' reservation.
In this case we could write

     (presence_set "slot1" "slot0 b0")

   The third construction (`final_presence_set') is analogous to
`presence_set'.  The difference between them is when checking is done.
When an instruction is issued in given automaton state reflecting all
current and planned unit reservations, the automaton state is changed.
The first state is a source state, the second one is a result state.
Checking for `presence_set' is done on the source state reservation,
checking for `final_presence_set' is done on the result reservation.
This construction is useful to describe a reservation which is actually
two subsequent reservations.  For example, if we use

     (presence_set "slot1" "slot0")

   the following insn will be never issued (because `slot1' requires
`slot0' which is absent in the source state).

     (define_reservation "insn_and_nop" "slot0 + slot1")

   but it can be issued if we use analogous `final_presence_set'.

   The forth construction (`absence_set') means that each functional
unit in the first string can be reserved only if each pattern of units
whose names are in the second string is not reserved.  This is an
asymmetric relation (actually `exclusion_set' is analogous to this one
but it is symmetric).  For example, it is useful for description that
VLIW `slot0' can not be reserved after `slot1' or `slot2' reservation.
We could describe it by the following construction

     (absence_set "slot2" "slot0, slot1")

   Or `slot2' can not be reserved if `slot0' and unit `b0' are reserved
or `slot1' and unit `b1' are reserved.  In this case we could write

     (absence_set "slot2" "slot0 b0, slot1 b1")

   All functional units mentioned in a set should belong to the same
automaton.

   The last construction (`final_absence_set') is analogous to
`absence_set' but checking is done on the result (state) reservation.
See comments for `final_presence_set'.

   You can control the generator of the pipeline hazard recognizer with
the following construction.

     (automata_option OPTIONS)

   OPTIONS is a string giving options which affect the generated code.
Currently there are the following options:

   * "no-minimization" makes no minimization of the automaton.  This is
     only worth to do when we are debugging the description and need to
     look more accurately at reservations of states.

   * "time" means printing additional time statistics about generation
     of automata.

   * "v" means a generation of the file describing the result automata.
     The file has suffix `.dfa' and can be used for the description
     verification and debugging.

   * "w" means a generation of warning instead of error for
     non-critical errors.

   * "ndfa" makes nondeterministic finite state automata.  This affects
     the treatment of operator `|' in the regular expressions.  The
     usual treatment of the operator is to try the first alternative
     and, if the reservation is not possible, the second alternative.
     The nondeterministic treatment means trying all alternatives, some
     of them may be rejected by reservations in the subsequent insns.
     You can not query functional unit reservations in nondeterministic
     automaton states.

   As an example, consider a superscalar RISC machine which can issue
three insns (two integer insns and one floating point insn) on the
cycle but can finish only two insns.  To describe this, we define the
following functional units.

     (define_cpu_unit "i0_pipeline, i1_pipeline, f_pipeline")
     (define_cpu_unit "port0, port1")

   All simple integer insns can be executed in any integer pipeline and
their result is ready in two cycles.  The simple integer insns are
issued into the first pipeline unless it is reserved, otherwise they
are issued into the second pipeline.  Integer division and
multiplication insns can be executed only in the second integer
pipeline and their results are ready correspondingly in 8 and 4 cycles.
The integer division is not pipelined, i.e. the subsequent integer
division insn can not be issued until the current division insn
finished.  Floating point insns are fully pipelined and their results
are ready in 3 cycles.  Where the result of a floating point insn is
used by an integer insn, an additional delay of one cycle is incurred.
To describe all of this we could specify

     (define_cpu_unit "div")
     
     (define_insn_reservation "simple" 2 (eq_attr "type" "int")
                              "(i0_pipeline | i1_pipeline), (port0 | port1)")
     
     (define_insn_reservation "mult" 4 (eq_attr "type" "mult")
                              "i1_pipeline, nothing*2, (port0 | port1)")
     
     (define_insn_reservation "div" 8 (eq_attr "type" "div")
                              "i1_pipeline, div*7, div + (port0 | port1)")
     
     (define_insn_reservation "float" 3 (eq_attr "type" "float")
                              "f_pipeline, nothing, (port0 | port1))
     
     (define_bypass 4 "float" "simple,mult,div")

   To simplify the description we could describe the following
reservation

     (define_reservation "finish" "port0|port1")

   and use it in all `define_insn_reservation' as in the following
construction

     (define_insn_reservation "simple" 2 (eq_attr "type" "int")
                              "(i0_pipeline | i1_pipeline), finish")


File: gccint.info,  Node: Comparison of the two descriptions,  Prev: Automaton pipeline description,  Up: Processor pipeline description

Drawbacks of the old pipeline description
.........................................

   The old instruction level parallelism description and the pipeline
hazards recognizer based on it have the following drawbacks in
comparison with the DFA-based ones:

   * Each functional unit is believed to be reserved at the instruction
     execution start.  This is a very inaccurate model for modern
     processors.

   * An inadequate description of instruction latency times.  The
     latency time is bound with a functional unit reserved by an
     instruction not with the instruction itself.  In other words, the
     description is oriented to describe at most one unit reservation
     by each instruction.  It also does not permit to describe special
     bypasses between instruction pairs.

   * The implementation of the pipeline hazard recognizer interface has
     constraints on number of functional units.  This is a number of
     bits in integer on the host machine.

   * The interface to the pipeline hazard recognizer is more complex
     than one to the automaton based pipeline recognizer.

   * An unnatural description when you write a unit and a condition
     which selects instructions using the unit.  Writing all unit
     reservations for an instruction (an instruction class) is more
     natural.

   * The recognition of the interlock delays has a slow implementation.
     The GCC scheduler supports structures which describe the unit
     reservations.  The more functional units a processor has, the
     slower its pipeline hazard recognizer will be.  Such an
     implementation would become even slower when we allowed to reserve
     functional units not only at the instruction execution start.  In
     an automaton based pipeline hazard recognizer, speed is not
     dependent on processor complexity.

