123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431 |
- .NH 2
- Definition of the intermediate code
- .PP
- The intermediate code of the optimizer consists
- of several components:
- .IP -
- the object table
- .IP -
- the procedure table
- .IP -
- the em code
- .IP -
- the control flow graphs
- .IP -
- the loop table
- .LP -
- .PP
- These components are described in
- the next sections.
- The syntactic structure of every component
- is described by a set of context free syntax rules,
- with the following conventions:
- .DS
- .TS
- l l.
- x a non-terminal symbol
- A a terminal symbol (in capitals)
- x: a b c; a grammar rule
- a | b a or b
- (a)+ 1 or more occurrences of a
- {a} 0 or more occurrences of a
- .TE
- .DE
- .NH 3
- The object table
- .PP
- EM programs declare blocks of bytes rather than (global) variables.
- A typical program may declare 'HOL 7780'
- to allocate space for 8 I/O buffers,
- 2 large arrays and 10 scalar variables.
- The optimizer wants to deal with
- .UL objects
- like variables, buffers and arrays
- and certainly not with huge numbers of bytes.
- Therefore the intermediate code contains information
- about which global objects are used.
- This information can be obtained from an EM program
- by just looking at the operands of instruction
- such as LOE, LAE, LDE, STE, SDE, INE, DEE and ZRE.
- .PP
- The object table consists of a list of
- .UL datablock
- entries.
- Each such entry represents a declaration like HOL, BSS,
- CON or ROM.
- There are five kinds of datablock entries.
- The fifth kind,
- UNKNOWN, denotes a declaration in a
- separately compiled file that is not made
- available to the optimizer.
- Each datablock entry contains the type of the block,
- its size, and a description of the objects that
- belong to it.
- If it is a rom,
- it also contains a list of values given
- as arguments to the rom instruction,
- provided that this list contains only integer numbers.
- An object has an offset (within its datablock)
- and a size.
- The size need not always be determinable.
- Both datablock and object contain a unique
- identifying number
- (see previous section for their use).
- .DS
- .UL syntax
- .TS
- lw(1i) l l.
- object_table:
- {datablock} ;
- datablock:
- D_ID -- unique identifying number
- PSEUDO -- one of ROM,CON,BSS,HOL,UNKNOWN
- SIZE -- # bytes declared
- FLAGS
- {value} -- contents of rom
- {object} ; -- objects of the datablock
- object:
- O_ID -- unique identifying number
- OFFSET -- offset within the datablock
- SIZE ; -- size of the object in bytes
- value:
- argument ;
- .TE
- .DE
- A data block has only one flag: "external", indicating
- whether the data label is externally visible.
- The syntax for "argument" will be given later on
- (see em_text).
- .NH 3
- The procedure table
- .PP
- The procedure table contains global information
- about all procedures that are made available
- to the optimizer
- and that are needed by the EM program.
- (Library units may not be needed, see section 3.5).
- The table has one entry for
- every procedure.
- .DS
- .UL syntax
- .TS
- lw(1i) l l.
- procedure_table:
- {procedure}
- procedure:
- P_ID -- unique identifying number
- #LABELS -- number of instruction labels
- #LOCALS -- number of bytes for locals
- #FORMALS -- number of bytes for formals
- FLAGS -- flag bits
- calling -- procedures called by this one
- change -- info about global variables changed
- use ; -- info about global variables used
- calling:
- {P_ID} ; -- procedures called
- change:
- ext -- external variables changed
- FLAGS ;
- use:
- FLAGS ;
- ext:
- {O_ID} ; -- a set of objects
- .TE
- .DE
- .PP
- The number of bytes of formal parameters accessed by
- a procedure is determined by the front ends and
- passed via a message (parameter message) to the optimizer.
- If the front end is not able to determine this number
- (e.g. the parameter may be an array of dynamic size or
- the procedure may have a variable number of arguments) the attribute
- contains the value 'UNKNOWN_SIZE'.
- .sp 0
- A procedure has the following flags:
- .IP -
- external: true if the proc. is externally visible
- .IP -
- bodyseen: true if its code is available as EM text
- .IP -
- calunknown: true if it calls a procedure that has its bodyseen
- flag not set
- .IP -
- environ: true if it uses or changes a (non-global) variable in
- a lexically enclosing procedure
- .IP -
- lpi: true if is used as operand of an lpi instruction, so
- it may be called indirect
- .LP
- The change and use attributes both have one flag: "indirect",
- indicating whether the procedure does a 'use indirect'
- or a 'store indirect' (indirect means through a pointer).
- .NH 3
- The EM text
- .PP
- The EM text contains the EM instructions.
- Every EM instruction has an operation code (opcode)
- and 0 or 1 operands.
- EM pseudo instructions can have more than
- 1 operand.
- The opcode is just a small (8 bit) integer.
- .sp
- There are several kinds of operands, which we will
- refer to as
- .UL types.
- Many EM instructions can have more than one type of operand.
- The types and their encodings in Compact Assembly Language
- are discussed extensively in.
- .[~[
- keizer architecture
- .], section 11.2]
- Of special interest is the way numeric values
- are represented.
- Of prime importance is the machine independency of
- the representation.
- Ultimately, one could store every integer
- just as a string of the characters '0' to '9'.
- As doing arithmetic on strings is awkward,
- Compact Assembly Language allows several alternatives.
- The main idea is to look at the value of the integer.
- Integers that fit in 16, 32 or 64 bits are
- represented as a row of resp. 2, 4 and 8 bytes,
- preceded by an indication of how many bytes are used.
- Longer integers are represented as strings;
- this is only allowed within pseudo instructions, however.
- This concept works very well for target machines
- with reasonable word sizes.
- At present, most ACK software cannot be used for word sizes
- higher than 32 bits,
- although the handles for using larger word sizes are
- present in the design of the EM code.
- In the intermediate code we essentially use the
- same ideas.
- We allow three representations of integers.
- .IP -
- integers that fit in a short are represented as a short
- .IP -
- integers that fit in a long but not in a short are represented
- as longs
- .IP -
- all remaining integers are represented as strings
- (only allowed in pseudos).
- .LP
- The terms short and long are defined in
- .[~[
- ritchie reference manual programming language
- .], section 4]
- and depend only on the source machine
- (i.e. the machine on which ACK runs),
- not on the target machines.
- For historical reasons a long will often be called an
- .UL offset.
- .PP
- Operands can also be instruction labels,
- objects or procedures.
- Instruction labels are denoted by a
- .UL label
- .UL identifier,
- which can be distinguished from a normal identifier.
- .sp
- The operand of a pseudo instruction can be a list of
- .UL arguments.
- Arguments can have the same type as operands, except
- for the type short, which is not used for arguments.
- Furthermore, an argument can be a string or
- a string representation of a signed integer, unsigned integer
- or floating point number.
- If the number of arguments is not fully determined by
- the pseudo instruction (e.g. a ROM pseudo can have any number
- of arguments), then the list is terminated by a special
- argument of type CEND.
- .DS
- .UL syntax
- .TS
- lw(1i) l l.
- em_text:
- {line} ;
- line:
- INSTR -- opcode
- OPTYPE -- operand type
- operand ;
- operand:
- empty | -- OPTYPE = NO
- SHORT | -- OPTYPE = SHORT
- OFFSET | -- OPTYPE = OFFSET
- LAB_ID | -- OPTYPE = INSTRLAB
- O_ID | -- OPTYPE = OBJECT
- P_ID | -- OPTYPE = PROCEDURE
- {argument} ; -- OPTYPE = LIST
- argument:
- ARGTYPE
- arg ;
- arg:
- empty | -- ARGTYPE = CEND
- OFFSET |
- LAB_ID |
- O_ID |
- P_ID |
- string | -- ARGTYPE = STRING
- const ; -- ARGTYPE = ICON,UCON or FCON
- string:
- LENGTH -- number of characters
- {CHARACTER} ;
- const:
- SIZE -- number of bytes
- string ; -- string representation of (un)signed
- -- or floating point constant
- .TE
- .DE
- .NH 3
- The control flow graphs
- .PP
- Each procedure can be divided
- into a number of basic blocks.
- A basic block is a piece of code with
- no jumps in, except at the beginning,
- and no jumps out, except at the end.
- .PP
- Every basic block has a set of
- .UL successors,
- which are basic blocks that can follow it immediately in
- the dynamic execution sequence.
- The
- .UL predecessors
- are the basic blocks of which this one
- is a successor.
- The successor and predecessor attributes
- of all basic blocks of a single procedure
- are said to form the
- .UL control
- .UL flow
- .UL graph
- of that procedure.
- .PP
- Another important attribute is the
- .UL immediate
- .UL dominator.
- A basic block B dominates a block C if
- every path in the graph from the procedure entry block
- to C goes through B.
- The immediate dominator of C is the closest dominator
- of C on any path from the entry block.
- (Note that the dominator relation is transitive,
- so the immediate dominator is well defined.)
- .PP
- A basic block also has an attribute containing
- the identifiers of every
- .UL loop
- that the block belongs to (see next section for loops).
- .DS
- .UL syntax
- .TS
- lw(1i) l l.
- control_flow_graph:
- {basic_block} ;
- basic_block:
- B_ID -- unique identifying number
- #INSTR -- number of EM instructions
- succ
- pred
- idom -- immediate dominator
- loops -- set of loops
- FLAGS ; -- flag bits
- succ:
- {B_ID} ;
- pred:
- {B_ID} ;
- idom:
- B_ID ;
- loops:
- {LP_ID} ;
- .TE
- .DE
- The flag bits can have the values 'firm' and 'strong',
- which are explained below.
- .NH 3
- The loop tables
- .PP
- Every procedure has an associated
- .UL loop
- .UL table
- containing information about all the loops
- in the procedure.
- Loops can be detected by a close inspection of
- the control flow graph.
- The main idea is to look for two basic blocks,
- B and C, for which the following holds:
- .IP -
- B is a successor of C
- .IP -
- B is a dominator of C
- .LP
- B is called the loop
- .UL entry
- and C is called the loop
- .UL end.
- Intuitively, C contains a jump backwards to
- the beginning of the loop (B).
- .PP
- A loop L1 is said to be
- .UL nested
- within loop L2 if all basic blocks of L1
- are also part of L2.
- It is important to note that loops could
- originally be written as a well structured for -or
- while loop or as a messy goto loop.
- Hence loops may partly overlap without one
- being nested inside the other.
- The
- .UL nesting
- .UL level
- of a loop is the number of loops in
- which it is nested (so it is 0 for
- an outermost loop).
- The details of loop detection will be discussed later.
- .PP
- It is often desirable to know whether a
- basic block gets executed during every iteration
- of a loop.
- This leads to the following definitions:
- .IP -
- A basic block B of a loop L is said to be a \fIfirm\fR block
- of L if B is executed on all successive iterations of L,
- with the only possible exception of the last iteration.
- .IP -
- A basic block B of a loop L is said to be a \fIstrong\fR block
- of L if B is executed on all successive iterations of L.
- .LP
- Note that a strong block is also a firm block.
- If a block is part of a conditional statement, it is neither
- strong nor firm, as it may be skipped during some iterations
- (see Fig. 3.2).
- .DS
- loop
- if cond1 then
- ... \kx-- this code will not
- \h'|\nxu'-- result in a firm or strong block
- end if;
- ... -- strong (always executed)
- exit when cond2;
- ... \kx-- firm (not executed on last iteration).
- end loop;
- Fig. 3.2 Example of firm and strong block
- .DE
- .DS
- .UL syntax
- .TS
- lw(1i) l l.
- looptable:
- {loop} ;
- loop:
- LP_ID -- unique identifying number
- LEVEL -- loop nesting level
- entry -- loop entry block
- end ;
- entry:
- B_ID ;
- end:
- B_ID ;
- .TE
- .DE
|