123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446 |
- .NH 2
- Implementation
- .PP
- A major factor in the implementation
- of Inline Substitution is the requirement
- not to use an excessive amount of memory.
- IL essentially analyzes the entire program;
- it makes decisions based on which procedure calls
- appear in the whole program.
- Yet, because of the memory restriction, it is
- not feasible to read the entire program
- in main memory.
- To solve this problem, the IL phase has been
- split up into three subphases that are executed sequentially:
- .IP 1.
- analyze every procedure; see how it accesses its parameters;
- simultaneously collect all calls
- appearing in the whole program an put them
- in a \fIcall-list\fR.
- .IP 2.
- use the call-list and decide which calls will be substituted
- in line.
- .IP 3.
- take the decisions of subphase 2 and modify the
- program accordingly.
- .LP
- Subphases 1 and 3 scan the input program; only
- subphase 3 modifies it.
- It is essential that the decisions can be made
- in subphase 2
- without using the input program,
- provided that subphase 1 puts enough information
- in the call-list.
- Subphase 2 keeps the entire call-list in main memory
- and repeatedly scans it, to
- find the next best candidate for expansion.
- .PP
- We will specify the
- data structures used by IL before
- describing the subphases.
- .NH 3
- Data structures
- .NH 4
- The procedure table
- .PP
- In subphase 1 information is gathered about every procedure
- and added to the procedure table.
- This information is used by the heuristic rules.
- A proctable entry for procedure p has
- the following extra information:
- .IP -
- is it allowed to substitute an invocation of p in line?
- .IP -
- is it allowed to put any parameter of such a call in line?
- .IP -
- the size of p (number of EM instructions)
- .IP -
- does p 'fall through'?
- .IP -
- a description of the formal parameters that p accesses; this information
- is obtained by looking at the code of p. For every parameter f,
- we record:
- .RS
- .IP -
- the offset of f
- .IP -
- the type of f (word, double word, pointer)
- .IP -
- may the corresponding actual parameter be put in line?
- .IP -
- is f ever accessed indirectly?
- .IP -
- if f used: never, once or more than once?
- .RE
- .IP -
- the number of times p is called (see below)
- .IP -
- the file address of its call-count information (see below).
- .LP
- .NH 4
- Call-count information
- .PP
- As a result of Inline Substitution, some procedures may
- become useless, because all their invocations have been
- substituted in line.
- One of the tasks of IL is to keep track which
- procedures are no longer called.
- Note that IL is especially keen on procedures that are
- called only once
- (possibly as a result of expanding all other calls to it).
- So we want to know how many times a procedure
- is called \fIduring\fR Inline Substitution.
- It is not good enough to compute this
- information afterwards.
- The task is rather complex, because
- the number of times a procedure is called
- varies during the entire process:
- .IP 1.
- If a call to p is substituted in line,
- the number of calls to p gets decremented by 1.
- .IP 2.
- If a call to p is substituted in line,
- and p contains n calls to q, then the number of calls to q
- gets incremented by n.
- .IP 3.
- If a procedure p is removed (because it is no
- longer called) and p contains n calls to q,
- then the number of calls to q gets decremented by n.
- .LP
- (Note that p may be the same as q, if p is recursive).
- .sp 0
- So we actually want to have the following information:
- .DS
- NRCALL(p,q) = number of call to q appearing in p,
- for all procedures p and q that may be put in line.
- .DE
- This information, called \fIcall-count information\fR is
- computed by the first subphase.
- It is stored in a file.
- It is represented as a number of lists, rather than as
- a (very sparse) matrix.
- Every procedure has a list of (proc,count) pairs,
- telling which procedures it calls, and how many times.
- The file address of its call-count list is stored
- in its proctable entry.
- Whenever this information is needed, it is fetched from
- the file, using direct access.
- The proctable entry also contains the number of times
- a procedure is called, at any moment.
- .NH 4
- The call-list
- .PP
- The call-list is the major data structure use by IL.
- Every item of the list describes one procedure call.
- It contains the following attributes:
- .IP -
- the calling procedure (caller)
- .IP -
- the called procedure (callee)
- .IP -
- identification of the CAL instruction (sequence number)
- .IP -
- the loop nesting level; our heuristic rules appreciate
- calls inside a loop (or even inside a loop nested inside
- another loop, etc.) more than other calls
- .IP -
- the actual parameter expressions involved in the call;
- for every actual, we record:
- .RS
- .IP -
- the EM code of the expression
- .IP -
- the number of bytes of its result (size)
- .IP -
- an indication if the actual may be put in line
- .RE
- .LP
- The structure of the call-list is rather complex.
- Whenever a call is expanded in line, new calls
- will suddenly appear in the program,
- that were not contained in the original body
- of the calling subroutine.
- These calls are inherited from the called procedure.
- We will refer to these invocations as \fInested calls\fR
- (see Fig. 5.1).
- .DS
- .TS
- lw(2.5i) l.
- procedure p is
- begin .
- a(); .
- b(); .
- end;
- .TE
- .TS
- lw(2.5i) l.
- procedure r is procedure r is
- begin begin
- x(); x();
- p(); -- in line a(); -- nested call
- y(); b(); -- nested call
- end; y();
- end;
- .TE
- Fig. 5.1 Example of nested procedure calls
- .DE
- Nested calls may subsequently be put in line too
- (probably resulting in a yet deeper nesting level, etc.).
- So the call-list does not always reflect the source program,
- but changes dynamically, as decisions are made.
- If a call to p is expanded, all calls appearing in p
- will be added to the call-list.
- .sp 0
- A convenient and elegant way to represent
- the call-list is to use a LISP-like list.
- .[
- poel lisp trac
- .]
- Calls that appear at the same level
- are linked in the CDR direction. If a call C
- to a procedure p is expanded,
- all calls appearing in p are put in a sub-list
- of C, i.e. in its CAR.
- In the example above, before the decision
- to expand the call to p is made, the
- call-list of procedure r looks like:
- .DS
- (call-to-x, call-to-p, call-to-y)
- .DE
- After the decision, it looks like:
- .DS
- (call-to-x, (call-to-p*, call-to-a, call-to-b), call-to-y)
- .DE
- The call to p is marked, because it has been
- substituted.
- Whenever IL wants to traverse the call-list of some procedure,
- it uses the well-known LISP technique of
- recursion in the CAR direction and
- iteration in the CDR direction
- (see page 1.19-2 of
- .[
- poel lisp trac
- .]
- ).
- All list traversals look like:
- .DS
- traverse(list)
- {
- for (c = first(list); c != 0; c = CDR(c)) {
- if (c is marked) {
- traverse(CAR(c));
- } else {
- do something with c
- }
- }
- }
- .DE
- The entire call-list consists of a number of LISP-like lists,
- one for every procedure.
- The proctable entry of a procedure contains a pointer
- to the beginning of the list.
- .NH 3
- The first subphase: procedure analysis
- .PP
- The tasks of the first subphase are to determine
- several attributes of every procedure
- and to construct the basic call-list,
- i.e. without nested calls.
- The size of a procedure is determined
- by simply counting its EM instructions.
- Pseudo instructions are skipped.
- A procedure does not 'fall through' if its CFG
- contains a basic block
- that is not the last block of the CFG and
- that ends on a RET instruction.
- The formal parameters of a procedure are determined
- by inspection of
- its code.
- .PP
- The call-list in constructed by looking at all CAL instructions
- appearing in the program.
- The call-list should only contain calls to procedures
- that may be put in line.
- This fact is only known if the procedure was
- analyzed earlier.
- If a call to a procedure p appears in the program
- before the body of p,
- the call will always be put in the call-list.
- If p is later found to be unsuitable,
- the call will be removed from the list by the
- second subphase.
- .PP
- An important issue is the recognition
- of the actual parameter expressions of the call.
- The front ends produces messages telling how many
- bytes of formal parameters every procedure accesses.
- (If there is no such message for a procedure, it
- cannot be put in line).
- The actual parameters together must account for
- the same number of bytes.A recursive descent parser is used
- to parse side-effect free EM expressions.
- It uses a table and some
- auxiliary routines to determine
- how many bytes every EM instruction pops from the stack
- and how many bytes it pushes onto the stack.
- These numbers depend on the EM instruction, its argument,
- and the wordsize and pointersize of the target machine.
- Initially, the parser has to recognize the
- number of bytes specified in the formals-message,
- say N.
- Assume the first instruction before the CAL pops S bytes
- and pushes R bytes.
- If R > N, too many bytes are recognized
- and the parser fails.
- Else, it calls itself recursively to recognize the
- S bytes used as operand of the instruction.
- If it succeeds in doing so, it continues with the next instruction,
- i.e. the first instruction before the code recognized by
- the recursive call, to recognize N-R more bytes.
- The result is a number of EM instructions that collectively push N bytes.
- If an instruction is come across that has side-effects
- (e.g. a store or a procedure call) or of which R and S cannot
- be computed statically (e.g. a LOS), it fails.
- .sp 0
- Note that the parser traverses the code backwards.
- As EM code is essentially postfix code, the parser works top down.
- .PP
- If the parser fails to recognize the parameters, the call will not
- be substituted in line.
- If the parameters can be determined, they still have to
- match the formal parameters of the called procedure.
- This check is performed by the second subphase; it cannot be
- done here, because it is possible that the called
- procedure has not been analyzed yet.
- .PP
- The entire call-list is written to a file,
- to be processed by the second subphase.
- .NH 3
- The second subphase: making decisions
- .PP
- The task of the second subphase is quite easy
- to understand.
- It reads the call-list file,
- builds an incore call-list and deletes every
- call that may not be expanded in line (either because the called
- procedure may not be put in line, or because the actual parameters
- of the call do not match the formal parameters of the called procedure).
- It assigns a \fIpay-off\fR to every call,
- indicating how desirable it is to expand it.
- .PP
- The subphase repeatedly scans the call-list and takes
- the call with the highest ratio.
- The chosen one gets marked,
- and the call-list is extended with the nested calls,
- as described above.
- These nested calls are also assigned a ratio,
- and will be considered too during the next scans.
- .sp 0
- After every decision the number of times
- every procedure is called is updated, using
- the call-count information.
- Meanwhile, the subphase keeps track of the amount of space left
- available.
- If all space is used, or if there are no more calls left to
- be expanded, it exits this loop.
- Finally, calls to procedures that are called only
- once are also chosen.
- .PP
- The actual parameters of a call are only needed by
- this subphase to assign a ratio to a call.
- To save some space, these actuals are not kept in main memory.
- They are removed after the call has been read and a ratio
- has been assigned to it.
- So this subphase works with \fIabstracts\fR of calls.
- After all work has been done,
- the actual parameters of the chosen calls are retrieved
- from a file,
- as they are needed by the transformation subphase.
- .NH 3
- The third subphase: doing transformations
- .PP
- The third subphase makes the actual modifications to
- the EM text.
- It is directed by the decisions made in the previous subphase,
- as expressed via the call-list.
- The call-list read by this subphase contains
- only calls that were selected for expansion.
- The list is ordered in the same way as the EM text,
- i.e. if a call C1 appears before a call C2 in the call-list,
- C1 also appears before C2 in the EM text.
- So the EM text is traversed linearly,
- the calls that have to be substituted are determined
- and the modifications are made.
- If a procedure is come across that is no longer needed,
- it is simply not written to the output EM file.
- The substitution of a call takes place in distinct steps:
- .IP "change the calling sequence" 7
- .sp 0
- The actual parameter expressions are changed.
- Parameters that are put in line are removed.
- All remaining ones must store their result in a
- temporary local variable, rather than
- push it on the stack.
- The CAL instruction and any ASP (to pop actual parameters)
- or LFR (to fetch the result of a function)
- are deleted.
- .IP "fetch the text of the called procedure"
- .sp 0
- Direct disk access is used to to read the text of the
- called procedure.
- The file offset is obtained from the proctable entry.
- .IP "allocate bytes for locals and temporaries"
- .sp 0
- The local variables of the called procedure will be put in the
- stack frame of the calling procedure.
- The same applies to any temporary variables
- that hold the result of parameters
- that were not put in line.
- The proctable entry of the caller is updated.
- .IP "put a label after the CAL"
- .sp 0
- If the called procedure contains a RET (return) instruction
- somewhere in the middle of its text (i.e. it does
- not fall through), the RET must be changed into
- a BRA (branch), to jump over the
- remainder of the text.
- This label is not needed if the called
- procedure falls through.
- .IP "copy the text of the called procedure and modify it"
- .sp 0
- References to local variables of the called routine
- and to parameters that are not put in line
- are changed to refer to the
- new local of the caller.
- References to in line parameters are replaced
- by the actual parameter expression.
- Returns (RETs) are either deleted or
- replaced by a BRA.
- Messages containing information about local
- variables or parameters are changed.
- Global data declarations and the PRO and END pseudos
- are removed.
- Instruction labels and references to them are
- changed to make sure they do not have the
- same identifying number as
- labels in the calling procedure.
- .IP "insert the modified text"
- .sp 0
- The pseudos of the called procedure are put after the pseudos
- of the calling procedure.
- The real text of the callee is put at
- the place where the CAL was.
- .IP "take care of nested substitutions"
- .sp 0
- The expanded procedure may contain calls that
- have to be expanded too (nested calls).
- If the descriptor of this call contains actual
- parameter expressions,
- the code of the expressions has to be changed
- the same way as the code of the callee was changed.
- Next, the entire process of finding CALs and doing
- the substitutions is repeated recursively.
- .LP
|