Trailing-Edge
-
PDP-10 Archives
-
FORTRAN-10_Alpha_31-jul-86
-
graph.bli
There are 12 other files named graph.bli in the archive. Click here to see a list.
!COPYRIGHT (c) DIGITAL EQUIPMENT CORPORATION 1972, 1986
!ALL RIGHTS RESERVED.
!
!THIS SOFTWARE IS FURNISHED UNDER A LICENSE AND MAY BE USED AND COPIED
!ONLY IN ACCORDANCE WITH THE TERMS OF SUCH LICENSE AND WITH THE
!INCLUSION OF THE ABOVE COPYRIGHT NOTICE. THIS SOFTWARE OR ANY OTHER
!COPIES THEREOF MAY NOT BE PROVIDED OR OTHERWISE MADE AVAILABLE TO ANY
!OTHER PERSON. NO TITLE TO AND OWNERSHIP OF THE SOFTWARE IS HEREBY
!TRANSFERRED.
!
!THE INFORMATION IN THIS SOFTWARE IS SUBJECT TO CHANGE WITHOUT NOTICE
!AND SHOULD NOT BE CONSTRUED AS A COMMITMENT BY DIGITAL EQUIPMENT
!CORPORATION.
!
!DIGITAL ASSUMES NO RESPONSIBILITY FOR THE USE OR RELIABILITY OF ITS
!SOFTWARE ON EQUIPMENT WHICH IS NOT SUPPLIED BY DIGITAL.
!AUTHOR NORMA ABEL/DCE/SJW/JNG/AHM/EGM/AlB/TJK/MEM
MODULE GRAPH(RESERVE(0,1,2,3),SREG=#17,VREG=#15,FREG=#16,DREGS=4)=
BEGIN
! REQUIRES FIRST, TABLES, OPTMAC/LIST
GLOBAL BIND GRAPHV = #11^24 + 0^18 + #4504; ! Version Date: 22-Jan-85
%(
***** Begin Revision History *****
108 ----- ----- FIX RETURNING OF OPTIMIZERS WORDS
FOR SUBSUMPTION
109 ----- ----- REMOVE BOGUS CALL TO LOKEXIT FOR TERMINATION
LABEL OF AN INNER DO IN GRAPH
110 ----- ----- DELETE BAD RETURN ON NULL LOOP IN DOCOLLAPSE
111 ----- ----- CHANGE ERROR MESSAGES AND MAKE GRAPH SPACE
DYNAMIC
112 ----- ----- DO ERROR MESSAGES CORRECTLY
113 ----- ----- CORRECT ERROR STUFF AND FIX GLOBAL REFS
114 ----- ----- SAVSPACE THE UNIQUE VALUES LIST
115 ----- ----- DELETE CODE THAT CARES ABOUT MAKING
LABELS "ASSIGNED" TO PARMATERS OF
CALLS SUCCESSORS OF THE CALL
116 ----- ----- FIX DO DEPTH ABALYSIS TREE WALK NOT TO
NEED A STACK
***** Begin Version 4B *****
117 327 16688 DISCONTINUE OPTIMIZATION FOR CASES WHERE
POSTDOMINATORS ARE NOT ALL COMPUTED, (DCE)
118 330 17150 MAKE SURE THAT ENTRY STATEMENTS ARE NEVER
CONSIDERED INACCESSIBLE CODE!
119 333 17045 FIX ASSIGNED GO TO STATEMENTS WITHIN DO LOOPS.
LOOP MUST NOT BE OPTIMIZED!, (DCE)
120 361 18451 FIX JUMP TO LABEL OF INNER DO LOOP, (DCE)
121 372 18314 FIX DOCOLLAPSE TO RETURN SPACE CORRECTLY, (DCE)
122 374 ----- FIX MIS-SPELLING (IOBRAHCH), (DCE)
***** Begin Version 5 *****
123 VER5 ----- GRAPH ERR= FOR OPEN & CLOSE, (SJW)
124 443 QA656 WARNING + STOP OPT IF DISCOVER ILLEGAL DO
NESTING IN LNKEXTND IN HOOKUP, (SJW)
***** Begin Version 5A *****
125 535 21809 INNACCESSIBLE CODE WITH ZERO LINE NUMBER!
126 565 21810 EXTENDED RANGE DO LOOP IMPROPERLY GRAPHED, (DCE)
127 576 22798 GIVE LINE NUMBER CORRECTLY WHEN LOOP DETECTED
***** Begin Version 5B *****
128 637 24802 DO NOT DISCONTINUE OPTIMIZATION WHEN INFINITE
LOOP DETECTED. INSTEAD, FIX THE GRAPH SO ALL
STATEMENTS ARE ASSIGNED POSTDOMINATORS.
FIX INACCESSIBLE CODE FINDER TO CHECK FOR
ZERO PREDOMINATORS., (JNG)
129 716 26409 MARK LOOPS AS INELIGIBLE FOR GLOBAL REGISTER
OPTIMIZATIONS IF THEY CONTAIN LABELS WHICH CAN
BE REACHED DIRECTLY ON RETURN FROM SUBROUTINES, (DCE)
***** Begin Version 6 *****
130 1052 EGM 9-Feb-81 --------
Correct edit 361 for correct optimization of a transfer
out of an inner do, to main, to outer do terminus path.
131 1063 DCE 23-Apr-81 QAR5631
Add error detection for jumps into loops with no exits.
132 1066 EGM 12-May-81 Q10-05202
Do not use ISN in error messages if not pertinent.
134 1112 DCE 17-Jul-81 QAR5631
More work to get the local label counts right for nested loops
with inner references to outer labels.
Should make edit 1063 much more stable.
135 1125 DCE 24-Sep-81 -----
Once again for edit 1063. This time remove edit 443 which has
been found to be both unnecessary, and wrong! Also fix up two
more places where the local label count could become incorrect.
These deal mainly with nested DO loop situations.
136 1136 AHM 9-Oct-81 Q20-01652,Q20-01656
Make GRAPH know about END= and ERR= for some I/O statements.
And turn the SELECT into a CASE.
137 1137 DCE 20-Oct-81 -----
Prevent looping optimizer for inaccessible DO stmnt with jumps
into loop.
138 1140 DCE 21-Oct-81 -----
Same as 137, but for nested loops with only the inner loop having
entrances.
***** Begin Version 6A *****
139 1150 DCE 16-Feb-82 20-17292
Handle programs with ASSIGN statements properly.
Avoid unjustified error messages.
1164 EGM 12-Jul-82
Prevent loop in (the) SWAMP caused by incorrect information being
setup for LOKEXIT. In particular, for certain nested loops, allow
LOKEXIT to correctly determine it has a branch back into an inner
loop, instead of thinking it has an exit. This change brings the
code in line with the comments at the end of GRAPH.
***** End V7 Development *****
***** End Revision History *****
***** Begin Version 10 *****
2206 TFV 27-Jun-83
Add case to GRAPH for INQUIRE statements. It checks for ERR=
branches and hooks them up.
2271 AlB 17-Jan-84
Add compatibility check for extended range of a DO loop.
If ANSI extensions are being flagged, E236 is generated whenever
there is an exit and an entrance to a DO loop.
Routine:
LOKENTRANCE
2366 TJK 10-Jun-84
Fix DOMINATE and PDOMINATE to correctly calculate immediate
pre- and post-dominators. P1 wasn't being reset to HEAD for
each successor of HEAD, with the result that the "immediate"
dominator of each successor of HEAD dominated (or was equal
to) each of the "immediate" dominators of the preceding
successors of HEAD. The pre- and post-dominator trees still
worked, but were more pessimal than the correct ones.
***** End V10 Development *****
***** End Revision History *****
***** Begin Version 11 *****
4502 MEM 22-Jan-85
Modified GRAPH for the DELETE statement.
4503 MEM 22-Jan-85
Modified GRAPH for the REWRITE statement.
4504 MEM 22-Jan-85
Modified GRAPH for the UNLOCK statement.
ENDV11
)%
SWITCHES NOLIST;
REQUIRE FIRST.BLI;
REQUIRE TABLES.BLI;
SWITCHES LIST;
REQUIRE OPTMAC.BLI;
FORWARD
LNKREV(2),
LNKFWD(2),
HOOKUP(1),
GRAPH,
GPHBLD,
ASSLOOKER(1),
DOCOLLAPSE,
LOKENTRANCE,
LOKEXIT(1),
MAKLLL,
MOORE,
SANDBAG,
FLOOD,
DOMINATE,
REFLOOD,
PDOMINATE,
WALKER;
EXTERNAL
ASIPTR,
BOTTOM,
CORMAN,
EXITNO,
FGRAPH,
ISN,
LEND,
LOOP,
QQ,
RGRAPH,
TOP,
TBLSEARCH;
OWN P,PA,PB,PREV,PC;
OWN PO,P1,P2,P3,HEAD,TAIL;
MAP PHAZ2 PA:PB:PC:P:PREV;
MAP BASE TOP;
OWN OLDHEAD,DISCONFLG; ![637]
MAP PHAZ2 QQ;
OWN EXITLST;
OWN LLLNO,LLL,EPTR;
MAP PHAZ2 PO:P1:P2:P3:HEAD:TAIL;
OWN T; ![637]
MAP PHAZ2 P:PA;
MAP PHAZ2 OLDHEAD;
!++
! Several important things to keep in mind are:
!
! 1. Inner DO-loops are treated as single nodes in the graph.
!
! 2. Entrances into the loop are treated as branches from TOP.
!
! 3. Exits from the loop are treated as branches to LEND.
!
! 4. The graph is really two separate directed graphs, the forward
! graph (based on successor pointers), and the reverse graph
! (based on predecessor pointers).
!
! 5. The predecessor (PREDPTR) and successor (SUCPTR) lists are
! terminated by pointers to RGRAPH and FGRAPH, which both
! contain zero.
!
! 6. Although it is generally true that if A has a pointer to B on
! its successor list, then B has a pointer to A on its
! predecessor list, and vice versa, this is not always the
! case. However, these deviations seem to occur only around
! the beginnings and ends of current DO-loops. This is
! something I haven't looked into very much.
!
!
! Note that in the literature, the nodes of a program graph are usually
! basic blocks, i.e., a sequence of statements with no branches out of
! the block except at the end of the block, and no branches into the
! block except at the beginning of the block. These are different from
! what the local register allocator regards as basic blocks, which are
! more closely akin to what are referred to as intervals. In any case,
! the nodes of the graph built by GPHBLD are individual statements (with
! the consequent of a LOGICAL IF being treated as a separate statement).
! This may be thought of as building a graph whose nodes (i.e., basic
! blocks) are smaller than they have to be.
!
! Also note that there is some additional bookkeeping involved which I
! haven't mentioned and which probably isn't worth going into in detail.
!
! Pre- And Post-dominators -
!
! Pre-dominators are commonly referred to merely as dominators in the
! literature. A node X dominates a node Y if every path from TOP to Y
! passes through X. Usually a node is considered to dominate itself,
! making the dominance relation a reflexive partial order (shown below).
!
! Consider a few facts about the dominance relation. First of all, it
! is clear that TOP dominates every accessible node in the graph of the
! current DO-loop. At least, this is true based on the graph
! constructed, since TOP is treated as a predecessor of all statements
! which may be branched to from outside the DO-loop. Note that
! statements which are truly dominated by TOP are also dominated by the
! CONTINUE statement following it, distinguishing them from the other
! case (in which TOP is the sole dominator).
!
! Second, note that if X dominates Y, and X <> Y, then Y can't dominate
! X. This may be seen by considering some path from TOP to X. This may
! be shortened to a path from TOP to X which doesn't pass through X
! until the end. However, if Y dominates X the it must pass through Y
! before passing through X, which violates the assumption that X
! dominates Y. This makes dominance antisymmetric.
!
! Third, note that if X dominates Y and Y dominates Z, then X dominates
! Z. This is clear since any path from TOP to Z must pass though Y and
! hence must pass through X. This makes dominance transitive.
!
! Fourth, note that if X dominates Z and Y dominates Z, and X <> Y, then
! either X dominates Y or Y dominates X (but not both, since this would
! violate the antisymmetric condition). To see this, consider some path
! from TOP to Z. Since X and Y both dominate Z, the path must pass
! through both of them. By eliminating loops in the path, and possibly
! shortening it, we may reduce it to a path which passes through X, Y,
! and Z exactly once. Without loss of generality, assume that it passes
! through X before Y. Then X must dominate Y, since if it didn't we
! could find a path from TOP to Y which doesn't pass through X (or Z,
! since Y dominates Z), then continue from Y to Z without passing
! through X, which violates the assumption that X dominates Z.
! Similarly, if the path passes through Y before X, then Y must dominate
! X.
!
! We can now define the concept of immediate dominator. For every node
! Z other than TOP, there exists a node Y (other than Z) which dominates
! Z and is in turn dominated by every other dominator of Z (other than Z
! itself). This may be seen by considering all dominators of Z other
! than itself. Then pick some path from TOP to Z. This path must
! contain all dominators of Z. We may then eliminate loops and possibly
! shorten the path so that it contains all dominators of Z, and Z
! itself, exactly once. Let Y be the last dominator of Z in the path
! other than Z itself. Then, for every dominator X (other than Y and Z)
! of Z in the path, X must dominate Y (since Y can't dominate X).
! Therefore, Y is the (unique) immediate dominator of Z.
!
! It should be clear by now every node in the graph has a chain of
! dominators leading up to TOP, with each dominator in the chain being
! the immediate dominator of the node below it in the chain.
! Furthermore, it should be clear that the entire dominator structure of
! the graph may be represented by a tree, rooted at TOP, where the
! parent of each node in the tree is the immediate dominator of that
! node. This is, in fact, what the compiler creates when determining
! the pre-dominators of the graph.
!
! Similarly, the concept of post-dominance is a direct analogue to that
! of pre-dominance. A node Y is said to post-dominate a node X if every
! path from X to LEND passes through Y. It is clear that LEND
! post-dominates every node which isn't stuck in an infinite loop. The
! optimizer used to have problems dealing with such infinite loops,
! until edit 637 corrected the problem by adding links from what it
! considered to be the bottommost node in the infinite loop to LEND,
! then restarting the entire pre- and post-dominator algorithms, looping
! in this manner until no more infinite loops exit.
!
! The Basic Algorithm -
!
! The Moore Flood algorithm may be used to calculate pre- or
! post-dominators. The algorithm has two passes. Since the algorithm
! for post-dominators is essentially the same as the algorithm for
! pre-dominators (except that the reverse graph is used instead of the
! forward graph), the description following will describe the
! pre-dominator algorithm.
!
! The result of the algorithm is a dominator tree (i.e., a tree in which
! the parent of every node is its immediate dominator), and the BUSY
! list.
!
! 1. The first pass of the algorithm builds a tentative
! pre-dominator tree of every accessible node in the graph,
! assigns a LEVEL to every node in the tree, and computes the
! BUSY list. The tree it builds is rooted at TOP, with the
! parent of each node pointed to by PREDOM (i.e., the tentative
! immediate pre-dominator pointer). The parent of TOP is TOP.
! The LEVEL of each node (stored in the LEVEL field of that
! node) is one more than its depth in the tree (i.e., the LEVEL
! of TOP is 1). The BUSY list is a linked list of the nodes in
! the tree. The BUSY field of each node points to the next
! node in the list, which starts at TOP and ends with a zero
! pointer. The list includes every node in the tree, and the
! list is linked in ascending LEVEL order.
!
! The tree has the additional property that the LEVEL field of
! each node is as low as possible (i.e., the LEVEL field of
! each node is one more than the length of the shortest path
! from TOP to that node in the complete forward graph of the
! current DO-loop).
!
! The tree is constructed by first setting the LEVEL of TOP to
! 1 and the PREDOM of TOP to TOP. Two pointers into the BUSY
! list are kept as it and the tree are being built. One
! pointer (TAIL) points to the current end of the list; as
! each new node is visited, it is linked onto the end. The
! other pointer (HEAD) points to the first node in the list
! whose successor list hasn't been examined yet. HEAD and TAIL
! both start out pointing to TOP.
!
! The algorithm then walks HEAD down the list (starting at
! TOP). For each value of HEAD, it examines all successors of
! the node HEAD points to. For each successor which hasn't
! been visited, it sets the LEVEL to one more than the LEVEL of
! HEAD, sets its PREDOM field to HEAD, and links it onto the
! end of the BUSY list. When all successors of the node
! pointed to by HEAD have been processed, it bumps HEAD to its
! successor in the BUSY list and loops. The algorithm
! terminates when HEAD becomes zero, meaning it has walked off
! the end of the BUSY list.
!
! This is the simpler pass of the algorithm, and it should be
! clear that the results of this pass (i.e., the tentative
! pre-dominator tree, the LEVEL field for each node in the
! tree, and the BUSY list) are what they're claimed to be.
!
! 2. The second pass of the algorithm turns the tree created by
! the first pass into the pre-dominator tree. Since the parent
! of each node X in the tree (other than TOP) has X as an
! immediate successor, it is clear that the immediate
! pre-dominator of every node in the tree is an ancestor of
! that node. Therefore, the final pre-dominator tree may be
! obtained by changing the parent (i.e., the PREDOM field) of
! each node with an incorrect parent to point to some other
! ancestor of itself in the tree.
!
! The algorithm basically iterates over the nodes in the tree,
! adjusting the tentative pre-dominator of each immediate
! successor to some ancestor of that successor (when the
! tentative pre-dominator is known to be incorrect). After
! it's looked at each node in the tree, it checks to see if any
! changes were made. If so, it repeats the process until no
! changes were made.
!
! To explain this in a bit more detail: For each pass over the
! tree, it walks the nodes in the tree in BUSY list order
! (starting at TOP). Then, for each node X, it examines each
! successor Y of that node. It sets a temporary P1 to X and a
! temporary P2 to the parent of Y. It then walks P1 and P2 up
! the tree until they converge, setting P1 to its parent if its
! LEVEL is >= the LEVEL of P2, otherwise setting P2 to its
! parent. Once P1 = P2, it compares this to the parent of Y
! (i.e., the initial value of P2). If it's different, it means
! P2 has changed, and it then sets the parent of Y to the new
! value and remembers that it's made a change. After walking
! the entire BUSY list, it checks to see if it made any
! changes. If so, it repeats the process until no changes were
! made.
!
! When this is done, the parent of each node in the tree is its
! immediate pre-dominator.
!
! Note that in the description of the algorithm, P1 and P2
! always converge to their closest common ancestor. To see
! that this is true, it is sufficient to note that neither will
! back up past their closest common ancestor. However, this is
! clear, since as soon as one of them becomes their closest
! common ancestor, if it is still unequal to the other, then it
! is an ancestor of the other, and therefore must have been an
! ancestor of the other in the original tree, and hence it has
! a lower LEVEL than the other, and the other will back up
! instead of it. The process always terminates, since if one
! of them ever reaches TOP, the other will keep backing up
! until it, too, has reached TOP.
!
! To show that the algorithm results in the pre-dominator tree
! that we desire, it is sufficient to show that:
!
! 1. At all times, each node remains a descendant of its
! immediate pre-dominator (except TOP, whose parent is
! always itself). This insures that no node is linked too
! high in the tree.
!
! 2. When the algorithm completes, the parent of each node
! pre-dominates that node. This insures that all nodes
! have been linked high enough in the tree.
!
!
! These two conditions clearly imply that the result is the
! pre-dominator tree we desire. Note that the only node whose
! parent can't be changed is TOP, which has already had its
! parent set to itself. Now to prove both conditions:
!
! 1. To show that the first condition is satisfied, consider
! some instance in which the tree is changed. Let X be the
! node whose successors are being considered for updating.
! Let Y be the successor of X being considerd. Let W be
! the current parent of Y. Now, assume that a change is
! actually occuring, with the parent of Y being changed to
! some node A (which is the closest common ancestor of X
! and W). Since a change is occurring, A <> W, although we
! allow A to be X. Let S be the subtree whose root is Y.
! Then the nodes of S are precisely those nodes which will
! lose an ancestor by the change. Now, let Q be some node
! in S (possibly Y). Let P be the immediate pre-dominator
! of Q. We need to show that P remains an ancestor of Q
! after the change.
!
! If P is in S, then the condition is satisfied. If P is A
! or some ancestor of A, then the condition is also
! satisfied. The only other possibility is that P is on
! the path in the tree from A to W, and possibly W itself
! (but not A). If this were the case, then Q would lose P
! as an ancestor, so we must show that this can't happen.
!
! First, note that P can't be an ancestor of X (or X
! itself). If it were, then P would be a common ancestor
! of X and W, which it isn't since it's a descendant of A
! (which is the closest common ancestor of X and W). Next,
! since P isn't an ancestor of X, then it doesn't
! pre-dominate X, and hence there must exist a path in the
! forward program graph from TOP to X which doesn't contain
! P (if X is TOP then we have a nil path). Then, since Y
! is a successor of X in the forward program graph, we have
! a path from TOP to Y in the forward program graph which
! doesn't contain P.
!
! Next, note that in the original tree (i.e., before the
! second pass of the algorithm), P was an ancestor of Y and
! Y was an ancestor of Q (or Q itself). This is clear
! since the second pass of the algorithm never gives a node
! a new ancestor. Therefore, since the original tree was a
! subset of the forward program graph, there exists a path
! in the forward program graph from Y to Q (possibly nil)
! which doesn't contain P. Concatenating this onto the
! path from TOP to Y which doesn't contain P yields a path
! from TOP to Q in the forward program graph which doesn't
! contain P. However, this contradicts the assumption that
! P is the immediate pre-dominator of Q, and therefore this
! case can't exist.
!
! This completes the proof of the first condition in the
! proof of the second pass of the algorithm.
!
! 2. To prove the second condition, suppose that after the
! algorithm completes we are left with one or more nodes
! whose parents don't pre-dominate them.
!
! Let D be the (non-empty) set of all nodes whose parents
! don't pre-dominate them. Let E be the subset of D whose
! nodes have the greatest depth in the tree (all nodes in E
! have the same depth). Define g(N) for all nodes in D to
! be the length of the shortest path from TOP to N in the
! forward program graph which doesn't contain N's parent.
! Let F be the subset of nodes of E for which the function
! g is a minimum.
!
! Let Q be an element of F. Let S be the parent of Q. Now
! choose some path from TOP to Q in the forward program
! graph whose length is g(Q) and which doesn't pass through
! S. Let R be the node in that path which immediately
! precedes Q, so the path looks like TOP,...,R,Q. Note
! that R may be TOP.
!
! Observe that the second pass of the algorithm insures
! that S is an ancestor of R. This is because Q is a
! successor of R, so S is the closest common ancestor of R
! and Q. Next, let C be the pre-dominator of R (possibly R
! itself) which is closest to S in the path in the tree
! from S to R. Note that C can't be S since S clearly
! doesn't pre-dominate R. Also note that the parent of C
! doesn't pre-dominate C, since it would then pre-dominate
! R and we would have chosen it for C. So C must be in D.
! We then have two cases:
!
! 1. The parent of C is S. Since C has the same depth as
! Q, C is also in E. Furthermore, since C
! pre-dominates R, it must be on the path we found from
! TOP to Q. However, the path we have from TOP to C is
! shorter than the path from TOP to Q, which violates
! the assumption that Q is in F. Therefore, the parent
! of C can't be S.
!
! 2. The parent of C is not S. In this case, the depth of
! C must be greater than the depth of Q, which violates
! the assumption that Q is in E. Therefore, the parent
! of C must be S, which is another contradiction.
! Therefore, the set D must be empty.
!
!
! We have shown that the set D must be empty. This
! completes the proof of the second condition in the proof
! of the second pass of the algorithm.
!
!
! This completes the proof of the second pass of the algorithm.
!
! The Implementation -
!
! FLOOD is the controlling routine for the pre- and post-dominator
! algorithms. The first pass of the Moore Flood algorithm for
! post-dominators is REFLOOD, the second pass for post-dominators is
! PDOMINATE, the first pass for pre-dominators is MOORE, and the second
! pass for pre-dominators is DOMINATE. We therefore have:
!
!
! Post-dominators Pre-dominators
! -------------- ---------------
! First pass REFLOOD MOORE
! Second pass PDOMINATE DOMINATE
!--
ROUTINE LNKREV(X,Q)=
BEGIN
REGISTER PHAZ2 GP:T;
MAP PHAZ2 Q;
!X IS THE PREDECESSOR OF Q
T_.Q[PREDPTR];
GP_GETGRAPHELM;
GP[CESLNK]_.T;
Q[PREDPTR]_.GP;
GP[CESSOR]_.X;
END; ! of LNKREV
ROUTINE LNKFWD(X,Q)=
BEGIN
MAP PHAZ2 Q;
REGISTER PHAZ2 GP:T;
!X IS THE SUCCESSOR FO Q
T_.Q[SUCPTR];
GP_GETGRAPHELM;
GP[CESLNK]_.T;
Q[SUCPTR]_.GP;
GP[CESSOR]_.X;
END; ! of LNKFWD
!FOR EACH LABEL THAT IS ENCOUNTERED AS A BRANCH THE
!ROUTINE LOKEXIT IS CALLED. THIS ROUTINE EXAMINES THE LLL (LOCAL
!LABEL LIST) AND EXITLST (EXIT LABEL LIST), ETC. TO
!DETERMINE THE NATURE OF THE BRANCH. THE ROUTINE RETURNS
! 0 LOCAL LABEL, BRANCH WITHIN GRAPH OF CURRENT DO
! 1 EXIT, BOTTOM IS THE DESTINATION
! 2 IT IS A JUMP BACK TO A LABEL IN A NESTED DO
! PREVIOUSLY PROCESSED AND WILL BE CONSIDERED
! AS AN EXTENDED RANGE .PA[SNEXTND] IS THE DESTINATION
MACRO LNKBOT=
BEGIN
IF .P NEQ .LEND THEN
BEGIN
LNKFWD(.LEND,.P);
LNKREV(.P,.LEND);
END;
END$;
!
!NOTE: SXENTND POINTS TO THE DO DEPH ANALYSIS TREE SO WE NEED AN INDEIRECT
MACRO LNKEXTND =
BEGIN
PA_.PA[SNEXTND];
! DON'T ALLOW NODE TO BE ITS OWN PREDECESSOR: ONLY HAPPENS WHEN
! LOKEXIT RETURNS 2 => A LABEL ON EXTLST FOR THIS LOOP IS CONTAINED
! IN A LOOP WHICH IS CONTAINED IN THIS LOOP, IE, AN EXTENDED
! RANGE IS POSSIBLE. IF PREDPTR WOULD GET LOOPED, THE DO MUST CONTAIN
! AN ILLEGAL NEST, EG:
! DO 10 J = 1,10
! K = I + J
! IF (K+A .EQ. 0) GO TO 10
! DO 10 L = 1,5
!10 M = K + I + L + F
! Remove edit 443 - it had problems which are resolved elsewhere.
![1125]
![1125] IF .P EQL .PA [DOSRC]
![1125] THEN BEGIN
![1125] EXTERNAL CSTMNT, ISN, OPTERR, E140;
![1125] MAP BASE CSTMNT;
![1125] CSTMNT _ .PA [DOSRC]; !POINT TO ENCLOSING DO
![1125] ISN _ .CSTMNT [SRCISN]; !GET STATEMENT # FOR WARNING
![1125] OPTERR (E140); !ILLEGAL DO NESTING - OPT DISCONTINUED
![1125] END;
LNKFWD(.PA[DOSRC],.P);
LNKREV(.P,.PA[DOSRC]);
END$;
MACRO IOBRANCH=
BEGIN
IF .P[IOERR] NEQ 0 THEN
BEGIN
PA_.P[IOERR];
HOOKUP(.PA);
END;
IF .P[IOEND] NEQ 0 THEN
BEGIN
PA_.P[IOEND];
HOOKUP(.PA);
END;
%1136% PREV=.P
END$;
ROUTINE HOOKUP(PA)=
!TO SHORTEN CODE THIS ROUTINE WAS CREATED TO CALL LOKEXIT TO
!DETERMINE THE NATURE OF A BRANCH AND LINK IT INTO THE GRAPH
!CORRECTLY
BEGIN
MAP BASE PA;
CASE LOKEXIT(.PA) OF SET
BEGIN
LNKREV(.P,.PA[SNHDR]);
LNKFWD(.PA[SNHDR],.P);
END;
LNKBOT;
LNKEXTND
TES;
END; ! of HOOKUP
![637] Delete ABSGOCHK routine
ROUTINE GRAPH=
!++
! BUILD THE PROGRAM GRAPH FOR EACH INDIVIDUAL STATEMENT.
! P POINTS TO THE CURRENT STATEMENT.
! PREV POINTS TO THE PREVIOUS STATEMENT OR IS ZERO IF THE PREVIOUS
! STATEMENT WAS AN ABSOLUTE BRANCH.
!
! GRAPH looks at the current statement. For all statements that may
! be branched to by the current statement, it adds predecessor and
! successor pointers. However, if the label is outside of the current
! DO-loop, it uses LEND, and if the label is inside a nested DO-loop,
! it uses the DO statement of the outermost DO-loop which both
! contains the label and is within the current DO-loop. It also adds
! predecessor and successor pointers between the current statement and
! the statement immediately preceding it (unless that statement is an
! unconditional branch). Most of the actual connecting is done by the
! routine HOOKUP.
!--
BEGIN
! A special check for unconditional branches which may branch
! to themselves is also made, and if found a warning message
! is given warning of a potential infinite loop. This is done
! through the macro INFLOOP. However, in all of these cases
! the label will already have been moved to an optimizer
! created CONTINUE statement (in routine LABLADJ), so this is
! a useless, always-false test.
MACRO INFLOOP=
IF .PA EQL .P[SRCLBL] THEN OPTERR(E100)$;
%1136% MACRO OTHERS=PREV_.P$; ! Action for non-branch statements
EXTERNAL ENTRY,OPTERR,LOOP,LEND;
IF .PREV NEQ 0 THEN
BEGIN
LNKREV(.PREV,.P); LNKFWD(.P,.PREV);
END;
![1136] Create the CASE statement below from a vary large, slow SELECT
![1136] Also, make all I/O use IOBRANCH macro
CASE .P[SRCID] OF SET
OTHERS; ! Assignment
OTHERS; ! ASSIGN
BEGIN ! CALL
!NEED TO CHECK FOR LABELS AS PARAMETERS AND ASSIGN-ED VARIABLES
!
IF .P[CALLIST] NEQ 0 THEN
BEGIN
LOCAL ARGUMENTLIST AG;
AG_.P[CALLIST];
INCR I FROM 1 TO .AG[ARGCOUNT] DO
BEGIN
PA_.AG[.I,ARGNPTR];
IF .PA[OPRCLS] EQL LABOP THEN
BEGIN !LABEL AS PARAMETER
HOOKUP(.PA);
P[LABLARGS]_1;
END;
END; !INCR LOOP ON PARAMETERS
END; !PARAMETERS AT ALL
PREV_.P;
END; ! CALL
OTHERS; ! CONTINUE
BEGIN ! DO
! For DO-loops, it treats the DO-statement as
! potentially branching to every label on its exit
! list (i.e., the list of branches from within the
! DO-loop to labels outside of the DO-loop). In
! addition, it has the side effect of skipping the
! current statement past the body of the loop.
!NOTE THAT THIS IS AN INNER DO (ALREADY PROCESSED
!WE ADJUST PREV AND P TO START THE GRAPHING PROCESS
!UP AGAIN AT THE STATEMENT AFTER THE DO.
!THERE IS ONE OTHER THING TO DO:
!1. IF A PREVIOUS LOOP HAD A BRANCH OUT TO A LABEL
! WE MUST SEE IF THE LABEL IS DEFINED HEREIN (IN THE
! CURRENT LOOP AND LINK THEM UP.
!1 FIRST. IF THERE ARE OPTIMIZERS WORDS TO GO WITH THIS LOOP
IF .P[SRCOPT] NEQ 0 THEN
BEGIN
!IF THERE WERE EXITS FROM THIS LOOP THEY
!ARE IN A LINKED LIST FROM EXTLST
IF .P[EXTLST] NEQ 0 THEN
BEGIN
!EXAMINE THE LABELS ON THE LINKED LIST
!AND SEE IF THEY ARE IN LLL (LOCAL LABEL
!LIST.
PC_.P[EXTLST];
WHILE .PC NEQ 0 DO
BEGIN
! So that HOOKUP won't change it!
%1112% LOCAL SAVLREFCNT;
PA_.PC[LEFTP];
%1112% SAVLREFCNT_.PA[LREFCNT];
HOOKUP(.PA);
%1112% PA[LREFCNT]_.SAVLREFCNT;
!LOOK AT NEXT ITEM OM LINKED LIST
PC_.PC[RIGHTP];
END;
END; !EXTLST IS ZERO
END;
P_.P[DOLBL]; !TERMINATION LABEL
P_.P[SNHDR]; !TERMINATION STATEMENT
PREV_.P;
END; ! DO
BEGIN ! ENTRY, SUBROUTINE OR FUNCTION STATEMENT
!THIS SHOULD BE AN ENTRY, WE ARE IN THE "MAIN" PROGRAM
LNKFWD(.P,.TOP);
LNKREV(.TOP,.P);
PREV_.P;
END; ! ENTRY, SUBROUTINE OR FUNCTION STATEMENT
OTHERS; ! COMMON SUB
BEGIN ! GO TO
PA_.P[GOTOLBL];
INFLOOP;
HOOKUP(.PA);
PREV_0;
END; ! GO TO
BEGIN ! ASSIGNED GO TO
! For an ASSIGNED GOTO statement without a
! user-supplied label list, it calls the routine
! ASSLOOKER to look for all ASSIGNs to the ASSIGNED
! GOTO variable, and uses this for the label list.
ENTRY_.P[SRCISN];
!TURN OFF GLOBAL REGISTER ALLOCATION
! FOR THIS LOOP ONLY.
TOP[HASRTRN]_1;
IF .P[GOTOLIST] EQL 0 THEN !OPTIONAL LIST IS NOT PRESENT
BEGIN !YOU LOSE
!PICK UP LIST THAT IS
ASSLOOKER(.P[AGOTOLBL]);!LINKED OFF
!ASIPTR. THROUGH ALL
!ASSIGN STATEMENTS
!BY PHASE 1.
!INTERPRETATION OF **THE STANDARD**
!IF WE HAVE HAD TO BUILD THE LIST, WE
!WILL (BY DEFINITION) GO TO A LABEL ON
!THE LIST. THAT MAKES THIS AN ABSOLUTE
!BRANCH AND IT WILL BE TREATED A SUCH
IF .P[GOTONUM] EQL 0 THEN
(P[GOTOLIST]_0; OPTERR(E62));
PREV_0;
END;
!OPTIONAL LIST IN NODE
!HURRAY!
DECR I FROM .P[GOTONUM]-1 TO 0 DO
BEGIN
PA_@(.P[GOTOLIST]+.I); !SAME AS COMPUTED GO TO
INFLOOP;
HOOKUP(.PA);
!THIS IS NOT AN ABSOLUTE BRANCH
PREV_.P;
END;
END; ! ASSIGNED GO TO
BEGIN ! COMPUTED GO TO
!A COMPUTED GOTO IS NOT AN ABSOLUTE BRANCH, SINCE IF THE
!INDEX IS OUT OF RANGE CONTROL IS TRANSFERRED TO THE NEXT
!STATEMENT.
DECR I FROM .P[GOTONUM]-1 TO 0 DO
BEGIN
PA_@(.P[GOTOLIST]+.I); !PA BOUND TO BASE
INFLOOP;
HOOKUP(.PA);
END;
PREV_.P;
END; ! COMPUTED GO TO
BEGIN ! ARITHMETIC IF
PA_.P[AIFLESS];
INFLOOP;
HOOKUP(.PA);
PA_.P[AIFEQL];
INFLOOP;
HOOKUP(.PA);
PA_.P[AIFGTR];
INFLOOP;
HOOKUP(.PA);
%637% PREV_0;
END; ! ARITHMETIC IF
BEGIN ! LOGICAL IF - ONLY TRICKY CASE
! The LOGICAL IF statement and its consequent (i.e.,
! LIFSTATE) are, for the purposes of graphing and most
! of the optimzer, treated as separate statements
! which are both linked into the graph. The
! consequent gets its own optimizer words, and GRAPH
! recurses on itself to finish linking the consequent
! into the graph.
!FIRST GET THE OPTIMIZERS CORE FOR THE STATEMENT
PC_.P; !SAVE P
P_.P[LIFSTATE];
NAME<LEFT>_5;
P[SRCOPT]_CORMAN();
P[SUCPTR]_FGRAPH[0];
P[PREDPTR]_RGRAPH[0];
P_.PC; !RESTORE P
!THE IF STATEMENT BECOMES THE PREDECOESSOR OF LIFSTATE
LNKREV(.P,.P[LIFSTATE]);
!LIFSTATE BECOMES THE SUCCESSOR OF THE IF STATEMENT
LNKFWD(.P[LIFSTATE],.P);
!NOW THE TRICKY PART
! THE SUCCESSOR OF LIFSTATE
! **NOTE IT IS NOT THE NEXT STATEMENT IF LIFSTATE IS A BRANCH
!
PREV_0;
PC_.P; !SAVE P
P_.P[LIFSTATE]; !TRICK GRAPH
GRAPH();
!
!IF PREV IS NOT ZERO NOW IT WAS NOT A BRANCH STATEMENT
!
P_.PC; !RESTORE P
IF .PREV NEQ 0 THEN
BEGIN
!
!LIFSTATE IS A PREDECESSOR OF THE NEXT STATEMENT
LNKREV(.P[LIFSTATE],.P[SRCLINK]);
!
!THE NEXT STATEMENT IS A SUCCESSOR OF LIFSTATE
!
LNKFWD(.P[SRCLINK],.P[LIFSTATE]);
END ELSE P[TRUEISBR]_1;
!
PREV_.P;
END; ! LOGICAL IF
BEGIN ! RETURN
! STOP and RETURN statements are treated as
! unconditional branches to LEND.
LNKBOT;
%637% PREV_0;
TOP[HASRTRN]_1;
END; ! RETURN
BEGIN ! STOP
! STOP and RETURN statements are treated as
! unconditional branches to LEND.
LNKBOT;
%637% PREV_0;
END; ! STOP
IOBRANCH; ! READ
IOBRANCH; ! WRITE
%1136% IOBRANCH; ! DECODE
%1136% IOBRANCH; ! ENCODE
%1136% IOBRANCH; ! REREAD
%1136% IOBRANCH; ! FIND
IOBRANCH; ! CLOSE
%4502% IOBRANCH; ! DELETE
%4503% IOBRANCH; ! REWRITE
%1136% IOBRANCH; ! BACKSPACE
%1136% IOBRANCH; ! BACKFILE
%1136% IOBRANCH; ! REWIND
%1136% IOBRANCH; ! SKIPFILE
%1136% IOBRANCH; ! SKIPRECORD
%1136% IOBRANCH; ! UNLOAD
%4504% IOBRANCH; ! UNLOCK
%1136% IOBRANCH; ! ENDFILE
OTHERS; ! END
OTHERS; ! PAUSE
IOBRANCH; ! OPEN
OTHERS; ! Statement function
OTHERS; ! FORMAT
OTHERS; ! BLT
OTHERS; ! REGMASK
%2206% IOBRANCH; ! INQUIRE
TES;
!THIS ALL DOES NOT CATCH BRANCHES BACK OR CONNECT WITH
!INNER (MORE INNER, NOT NECESSARILY INNERMOST) LOOPS.
!TO DO THIS WE MUST LOOK AT THE LABEL OF THE STATEMENT, IF ANY,
!AND SEE IF THERE WAS A REFERENCE PREVIOUSLY MADE FROM THE
!*INSIDE*. SNEXTND IS A LABEL TABLE FIELD WHICH IS SET TO LOO
!IN MAKLLL AND UPDATED IN DOCOLLAPSE SO THAT IT POINTS TO
!THE OUTERMOST LOOP OF ANY NEST WHUCH CONTAINS THE LABEL IN QUESTION.
IF .P[SRCLBL] NEQ 0 THEN
BEGIN
PA_.P[SRCLBL];
![716] IF THIS LABEL CAN BE REACHED ON RETURN FROM SUBROUTINES
![716] THEN WE MUST MARK THE LOOP FOR NO GLOBAL REGISTER ALLOCATION
%716% IF .PA[SNRFS] NEQ 0 THEN TOP[HASRTRN]_1;
IF .PA[SNEXTND] NEQ 0 AND
.PA[SNEXTND] NEQ .LOOP AND
.PA[SNREFNO] NEQ 1 THEN
LNKEXTND;
END;
END; ! of GRAPH
GLOBAL ROUTINE GPHBLD=
!++
! GPHBLD is the routine which allocates the 5 extra optimizer words
! for each statement in the current loop, and builds the program graph
! for that loop.
!--
BEGIN
!BUILD THE FORWARD AND REVERSE GRAPHS FOR THE PROGRAM
!TOP IS FIRST STATEMENT
!BOTTOM IS LAST STATEMENT
EXTERNAL ISN,MOVLAB,LOOP;
EXTERNAL LEND,LOCELMIO,P2SKSTMNT,BACKST,SAVSPACE,CSTMNT;
%637% MAP BASE TOP:T:CSTMNT:LEND;
! First allocate the optimizer words for every statement from
! TOP to LEND, inclusive (in SRCLINK order), and initializes
! the predcessor and successor fields (PREDPTR and SUCPTR).
! Note that these are not initialized to zero, but are instead
! set to RGRAPH and FGRAPH (actually, the code uses RGRAPH[0]
! and FGRAPH[0], which is equivalent since the default
! structure VECTOR is being used.
P_.TOP;
!GET OPTIMIZERS SPECIAL 5 WORDS PER STATEMENT FOR EACH STATEMENT
!GET OPTIMIZERS WORDS FOR THIS STATEMENT (THE DO)
CSTMNT_.P;
ISN_.CSTMNT[SRCISN];
NAME<LEFT>_5;
P[SRCOPT]_CORMAN();
P[SUCPTR]_FGRAPH[0];
P[PREDPTR]_RGRAPH[0];
P_.P[SRCLINK];
!NO NEED TO RETRY THE ONE WE JUST DID
!NOW GET THEM FOR THE STATEMENT IN THE LOOP
WHILE .P NEQ .BOTTOM DO
BEGIN
IF .P[SRCID] NEQ DOID AND .P[SRCOPT] EQL 0
THEN
BEGIN
CSTMNT_.P;
NAME<LEFT>_5;
P[SRCOPT]_CORMAN();
P[SUCPTR]_FGRAPH[0];
P[PREDPTR]_RGRAPH[0];
END
ELSE
IF .P[SRCID] EQL DOID
THEN
BEGIN
T_.P[DOLBL];
P_PREV_.T[SNHDR];
!P WILL BE ADJUSTED IN THE STATEMNT AFTER THE NEXT END
END;
P_.P[SRCLINK];
END;
! Call MAKLLL to make a list of all labels local to the
! current loop, skipping over nested DO-loops. The list is
! linked through the SNNXTLAB field of the labels, headed by
! TOP[DOLBL] (the label of the last statement in the DO-loop).
MAKLLL(); !COLLECT LOCAL LABLES
!IF THIS IS REALLY A LOOP (I.E. NOT THE MAIN PROGRAM) THEN
!MAKE LEND A PREDECESSOR OF TOP.
!THIS IS TO HANDLE THE CASE ILLUSTRATED BY THE EXAMPLE:
! DO 10 -------
! = A
! .
! .
! .
! A =
! 10
!IF IT WERE NOT DONE THE DEFINITION POINT OF A AT ITS USE WOULD
!INDICATE THAT A WAS A REGION CONSTANT
IF .LOOP NEQ 0 THEN LNKREV(.LEND,.TOP);
!START THE GRAPH WITH THE STATEMENT AFTER THE DO LOOP
CSTMNT_PREV_.TOP;
P_.TOP[SRCLINK];
EXITNO_0; !INITIALIZE EXITNO
EPTR_0;
! Actually build the graph of the loop. Do this by calling
! GRAPH for each statement from TOP[SRCLINK] to BOTTOM,
! inclusive, in SRCLINK order. GRAPH looks at the current
! statement. For all statements that may be branched to by
! the current statement, it adds predecessor and successor
! pointers.
DO
BEGIN
CSTMNT_.P;
ISN_.CSTMNT[SRCISN];
GRAPH();
P_.P[SRCLINK];
END
UNTIL .P EQL .BOTTOM;
!IF THIS ISNT A MAIN PROGRAM AN THERE WERE LOOP EXITS
!GO FIND THE ENTRANCES
%1063% IF .LOOP NEQ 0 THEN
BEGIN
%1063% IF .EXITNO NEQ 0 THEN TOP[HASEXIT]_1;
LOKENTRANCE(); !COLLECT LOOP ENTRANCES
END;
!LEND STILL POINTS TO THE UNIQUE CONTINUE THAT GOES WITH THIS LOOP
!SAVE THE EXITLST INFO IN THE OPTINFO FIELD OF THIS CONTINUE
LEND[OPTINFO]_.EPTR;
END; ! of GPHBLD
ROUTINE ASSLOOKER(VAR)=
!++
! For an ASSIGNED GOTO statement without a user-supplied label list,
! ASSLOOKER looks for all ASSIGNs to the ASSIGNED GOTO variable, and uses
! this for the label list.
!--
!*****
!OBSCENITY IS IN THE EYE OF THE BEHOLDER
!*****
!IT STANDS FOR ASSIGN LOOKER
BEGIN
EXTERNAL OPTERR;
!LOOK AT LINKED LIST OF ASSIGN STATEMENTS
!VAR IS SYMBOL TABLE POINTER FOR ASSIGNED VARIABLE
!P IS STATEMENT POINTER
!FOR EACH MATCH ENCOUNTERER
!P IS PREDECESSOR OF *LABELED* STATEMENT
! *LABELED* STATEMENT IS PREDECESSOR OF STMT
MAP BASE PB;
MAP BASE VAR;
OWN BASE EXPR:CNT;
!SET A FLAG ON THE STATEMENT SO WE WILL
!REMOVE THE LIST LATER. REMOVINF THE LIST GIVES BETTER
!CODE.
P[NOLBLLST]_1;
PB_.ASIPTR<LEFT>; !PICK UP GLOBAL POINTER
!FIRST GO THROUGH THE LIST AND COUNT THE &'%$ LABELS
P[GOTONUM]_0;
WHILE .PB NEQ 0 DO
BEGIN
IF .VAR EQL .PB[ASISYM] THEN
P[GOTONUM]_.P[GOTONUM]+1 !UP COUNT
ELSE
!SPECIAL *TRY HARDER* FOR ARRAY REFERENCES
BEGIN
IF .VAR[OPRCLS] EQL ARRAYREF THEN
BEGIN
EXPR_.PB[ASISYM];
IF .EXPR[OPRCLS] EQL ARRAYREF THEN
IF .VAR[ARG1PTR] EQL .EXPR[ARG1PTR] THEN
!USE THIS ONE
P[GOTONUM]_.P[GOTONUM]+1; !UP COUNT
END;
END;
PB_.PB[ASILINK];
END;
!NOW WE KNOW HOW MANY THERE ARE. IF NONE GENERATE ERROR AND QUIT
IF .P[GOTONUM] EQL 0 THEN
BEGIN
OPTERR(E62);
RETURN;
END;
!RESET PB. GET CORE FOR LIST
PB_.ASIPTR<LEFT>;
NAME<LEFT>_.P[GOTONUM];
P[GOTOLIST]_CORMAN();
CNT_0;
WHILE .PB NEQ 0 DO
BEGIN
IF .VAR EQL .PB[ASISYM] THEN
BEGIN
!BUILD OPTIONAL LIST PROGRAMMER DID NOT PROVIDE
(.P[GOTOLIST]+.CNT)<RIGHT>_.PB[ASILBL];
CNT_.CNT+1;
END
ELSE
!SPECIAL *TRY HARDER* FOR ARRAY REFERENCES
BEGIN
IF .VAR[OPRCLS] EQL ARRAYREF THEN
BEGIN
EXPR_.PB[ASISYM];
IF .EXPR[OPRCLS] EQL ARRAYREF THEN
IF .VAR[ARG1PTR] EQL .EXPR[ARG1PTR] THEN
!USE THIS ONE
BEGIN
!BUILD OPTIONAL LIST PROGRAMMER DID NOT PROVIDE
(.P[GOTOLIST]+.CNT)<RIGHT>_.PB[ASILBL];
CNT_.CNT+1;
END;
END;
END;
PB_.PB[ASILINK];
END;
END; ! of ASSLOOKER
GLOBAL ROUTINE DOCOLLAPSE=
!++
! This routine is called from MRP2 after it is done optimizing the current
! DO-loop. It deallocates the extra words created by the optimizer and
! makes the loop seem like a single node in the graph (for when the graph
! of the next outer DO-loop is built).
!--
BEGIN
EXTERNAL LABTBL,SAVSPACE,OPTERR,LENTRY;
EXTERNAL BASE UNIQVAL;
MAP BASE T;
!CREATE A COLLAPSED DO NODE
! SUCCESSOR OF DO (IN GRAPH) IS
! STATEMENT FOLLOWING TERMINATION
! PLUS ALL OTHER EXITS
MAP PHAZ2 TOP:PB:BOTTOM;
TOP[PREDPTR]_RGRAPH[0]; !REINITIALIZE GRAPH POINTERS. PREDPTR WILL BE
TOP[SUCPTR]_FGRAPH[0]; ! FILLED BY GPHBLD FOR OUTER LOOP
TOP[LEVEL]_0; !INITIALIZE OTHER FIELDS
TOP[BUSY]_0;
TOP[PREDOM]_0;
TOP[POSTDOM]_0;
TOP[ACC]_0;
!MAKE A NEW BOTTOM.
!IT WILL BE LEND FOR THE PURPOSES OF COLLAPSING THE DO TO
!A SINGLE NODE
BOTTOM_.LEND;
!STEP THRU EXITLST BUILDING GRAPH
!FIRST GET OPTIMIZERS WORDS FOR BOTTOM IF THEY ARENT ALREADY THERER
IF .BOTTOM[SRCOPT] EQL 0 THEN
BEGIN
NAME<LEFT>_5;
BOTTOM[SRCOPT]_CORMAN();
END;
!AT ANY REATE REINITIALIZE THE GRAPHING FOR IT
BOTTOM[SUCPTR]_FGRAPH[0];
BOTTOM[PREDPTR]_RGRAPH[0];
!ZERO OTHER FIELDS
BOTTOM[BUSY]_BOTTOM[LEVEL]_BOTTOM[PREDOM]_BOTTOM[POSTDOM]_0;
BOTTOM[ACC]_0;
!HOOK TOP TO BOTTOM
LNKREV(.TOP,.BOTTOM);
LNKFWD(.BOTTOM,.TOP);
!PUT THE EXITLST INTO THE FIELD EXTLST
IF .EXITNO NEQ 0 THEN
TOP[EXTLST]_.EPTR;
!SAVE DOCHNGL FOR GLOBAL REGISTER ALLOCATION
!IN THE UNIQUE LABEL TABLE ENTRY THAT GOES WITH TOP
P_.TOP[DOLBL];
P[SNSTATUS]_.TOP[DOCHNGL];
!NOW GIVE BACK THE OPTIMIZERS WORDS FOR THE STATEMENTS IN THE
!LOOP. NOT FOR TOP OR BOTTOM, HOWEVER.
%1164% !ALSO UPDATE THE SNEXTND FIELD OF THE LABEL
%1164% !TABLE ENTRIES FOR ANY INNER LOOPS TO POINT TO
%1164% !THE OUTER-MORE LOOP WE ARE NOW COLLAPSING.
P_.TOP[SRCLINK];
WHILE .P NEQ .BOTTOM DO
BEGIN
IF .P[SRCOPT] NEQ 0 THEN
BEGIN
!GIVE BACK GRAPH ELEMENTS TOO
RELSGRAPHELM(P);
SAVSPACE(4,.P[SRCOPT]);
!DO NOT ALLOW ASSIGNED GO TO LISTS TO BE GIVEN
! BACK BY MORE THAN ONE DO LOOP! CLEAN UP TOO.
P[SRCOPT]_0;
!CHECK FOR ASSIGNED GO TO STATEMENTS AND
!LOGICAL IF STATEMENTS WHERE WE CAN CLEAN HOUSE
! FOR AN ASSIGNED GO TO STATEMENT, DELETE THE
! OPTIMIZER BUILT LIST
IF .P[SRCID] EQL AGOID AND .P[NOLBLLST] THEN
BEGIN
SAVSPACE(.P[GOTONUM]-1,.P[GOTOLIST]);
P[GOTONUM]_P[GOTOLIST]_0;
END
ELSE
IF .P[SRCID] EQL IFLID THEN
BEGIN
PC_.P[LIFSTATE];
IF .PC[SRCOPT] NEQ 0 THEN
BEGIN
RELSGRAPHELM(PC);
SAVSPACE(4,.PC[SRCOPT]);
PC[SRCOPT]_0;
IF .PC[SRCID] EQL AGOID AND
.PC[NOLBLLST] THEN
BEGIN
SAVSPACE(.PC[GOTONUM]-1,
.PC[GOTOLIST]);
PC[GOTONUM]_PC[GOTOLIST]_0;
END
END
END
END;
%1164% !Now walk any inner DOs
%1164% IF .P[SRCID] EQL DOID THEN
%1164% BEGIN
%1164% PB_.P[DOLBL]; !Get terminus node of inner loop
%1164% PB_.PB[SNHDR];
%1164% WHILE .P NEQ .PB DO !Until end of this inner loop
%1164% BEGIN !Graph elements discarded
%1164% ! during earlier collapse
%1164% IF .P[SRCLBL] NEQ 0 !If labeled, point
%1164% THEN !label at this loop
%1164% BEGIN
%1164% PA_.P[SRCLBL];
%1164% PA[SNEXTND]_.LOOP
%1164% END;
%1164% PREV_.P; !Keep track of one node back
%1164% P_.P[SRCLINK] !Next node in inner loop
%1164% END;
%1164% !Include the inner terminus label
%1164% PA_.P[SRCLBL];
%1164% PA[SNEXTND]_.LOOP;
%1164% P_.PREV !Drop back a node to allow
%1164% !outer loop to clean up graph
%1164% !elements for inner terminus
%1164% END;
P_.P[SRCLINK];
END;
!BECAUSE SUBSUMPTION MAY HAVE MOVED STATEMENTS WITH THE
!OPTIMIZERS WORDS INFRONT OF THE LOOP WE WILL ALSO LOOK
!BETWEEN LENTRY AND TOP
P_.LENTRY;
WHILE .P NEQ .TOP DO
BEGIN
IF .P[SRCOPT] NEQ 0 THEN
BEGIN
RELSGRAPHELM(P);
SAVSPACE(4,.P[SRCOPT]);
P[SRCOPT]_0;
END;
P_.P[SRCLINK];
END;
!RETURN THE SPACE CONSUMMED BY THE UNIQUE VALUE LIST
WHILE .UNIQVAL NEQ 0 DO
BEGIN
REGISTER BASE GP;
GP_.UNIQVAL[CLINK];
SAVSPACE(UNIQSIZ-1,.UNIQVAL);
UNIQVAL_.GP;
END;
END; ! of DOCOLLAPSE
ROUTINE LOKENTRANCE=
BEGIN
!AFTER GPHBLD WE CHECK OUT LLL TO SEE WHICH LABELS ARE LOOP
!ENTRANCES.
!THE STATEMENTS WHICH ARE ENTRANCES ARE PUT INTO THE GRAPH WITH TOP
!AS PREDECESSOR AND AS SUCCESSORS OF TOP TOP IN AFFECT WILL SERVE
!AS THE SUPER ENTRY.
!WE WILL ALSO CHECK TO SEE IF THE LOOP HAS NO EXITS AND SO THE
!CONTROL WORD AND INDUCTION VARIABLES MAY NOT NEED MATERIALIZATION.
![1063] Statement deleted.
![1063] IF .EXITNO EQL 0 THEN TOP[NEDSMATRLZ]_0;
PA_.TOP[DOLBL];
!PA POINTS TO TOP OF CHAIN OF LOCAL LABELS
!FOLLOW THAT CHAIN AND COMPARE REFERENCE COUNTS.
!IF THEY DONT MATCH ITS AN ENTRANCE. ZERO THE
!LABLE TABLE FIELDS WHILE YOUR HERE
WHILE .PA NEQ 0 DO
BEGIN
IF .PA[SNREFNO] NEQ .PA[LREFCNT] THEN
BEGIN
!THIS IS AN ENTRANCE
PB_.PA[SNHDR];
!DONT INCLUDE STATEMENTS THAT WILL MAKE
!BLOW-UPS OR FORMATS
IF .PB[SRCOPT] NEQ 0 THEN
BEGIN
%1063% EXTERNAL FATLERR,E151;
%2271% EXTERNAL WARNERR,E236;
!PUT THIS STATEMENT ON THE SUCCESSOR LIST FOR THE TOP OF
! THE LIST - NAMELY THE DO STATEMENT.
LNKFWD(.PB,.TOP);
LNKREV(.TOP,.PB);
!SET FLAG FOR GLOBAL ALLOCATOR USE
![1063] If loop entrances with absolutely no exits, then error!
%1150% IF NOT .PA[SNASSIGNED] THEN
%2271% IF .EXITNO EQL 0
%2271% THEN FATLERR(.PA[SNUMBER],0,E151<0,0>)
%2271% ELSE
%2271% IF FLAGANSI ! Warn about extended range
%2271% THEN WARNERR(.PA[SNUMBER],0,E236<0,0>);
TOP[HASENT]_1;
END;
END;
!ZERO THE FIELDS
PB_.PA[SNNXTLAB]; !SAVE POINTER
PA[SNNXTLAB]_0;
! Delete one unnecessary line
![1125] PA[LREFCNT]_0;
!RESTORE POINTER
PA_.PB;
END;
END; ! of LOKENTRANCE
ROUTINE LOKEXIT(LABLE)=
BEGIN
!SEARCH LLL FOR LABEL. IF NOT THERE IT IS A LOOP EXIT. ADD TO
!LOOP EXIT LIST.
EXTERNAL OPTERR,LOOP;
MAP BASE LLLNO:EXITLST;
LABEL WHLEXT;
MAP PEXPRNODE LABLE; ! (LABEL IS DELIBERATELY MISSPELLED.)
! Local label count needs to be incremented for this label reference.
%1112% LABLE[LREFCNT]_.LABLE[LREFCNT]+1;
!POINT TO TOP OF LINKED LIST OF LOCAL LABELS.
LLLNO_.TOP[DOLBL];
WHILE .LLLNO NEQ 0 DO
%1112% IF .LLLNO EQL .LABLE THEN RETURN 0
%1112% ELSE LLLNO_.LLLNO[SNNXTLAB];
!IF HERE LABEL WAS NOT ON LIST FOR CURRENT
!LOOK AT SNEXTND FIELD
IF .LABLE[SNEXTND] NEQ 0 AND
.LABLE[SNEXTND] NEQ .LOOP
AND NOT .TOP[INNERDOFLG] THEN
BEGIN
!CHECK TO BE REALLY SURE THAT THE LOOP WE ARE
!BRANCHING BACK INTO IS INNERMORE TO THE ONE
!CURRENTLY BEING PROCESSED.
REGISTER BASE T:T1;
T_.LABLE[SNEXTND];
T1_.TOP;
!LOOK THROUGH THE STATEMENTS IN THIS LOOP.
!T POINTS TO THE DO DEPTH ANALYSIS ENTRY
!FOR THE LOOP CONTINAING THE LABEL
WHILE .T1 NEQ .BOTTOM DO
BEGIN
!FOR THIS TO BE TRUE T1 SHOULD BE A DOLOOP
IF .T1 EQL .T[DOSRC] THEN RETURN (2);
T1_.T1[SRCLINK];
END;
END;
!IF WE ARE STILL IS THIS ROUTINE IT MUST BE AN EXIT
EXITLST_.EPTR;
!EPTR WAS SET IN THE MAIN BODY OF GPHBLD
WHLEXT:
!THE WHILE TAKES CARE OF THE INITIAL CONDITION
WHILE .EXITLST NEQ 0 DO
BEGIN
!THE THE LABEL IS ALREADY THERE JUST EXIT WITH THE
!CORRECT VALUE
IF .EXITLST[ELBL] EQL .LABLE THEN RETURN 1;
!NOW FOR THE TERMINATING CONDITION
IF .EXITLST[CLINK] NEQ 0 THEN
EXITLST_.EXITLST[CLINK]
ELSE
LEAVE WHLEXT;
END;
!HERE WE KNOW WE HAVE TO ADD ON TO THE LIST AND THAT EXITLST
!POINTS TO THE END OF THE LIST
NAME<LEFT>_1;
IF .EPTR EQL 0 THEN
EXITLST_CORMAN()
ELSE
EXITLST_EXITLST[CLINK]_CORMAN();
!FILL IS THE LABLE FIELD
EXITLST[ELBL]_.LABLE;
EXITNO_.EXITNO+1;
!BE SURE TO SET EPTR
IF .EPTR EQL 0 THEN EPTR_.EXITLST;
RETURN 1;
END; ! of LOKEXIT
ROUTINE MAKLLL=
BEGIN
!CREATE A LINKED LIST OF THE LOCAL LABELS IN THE CURRENT LOOP. THE
!LINKS ARE KEPT IN THE SNNXTLAB FIELD OF THE LABEL TABLE.
!TOP[DOLBL] (the label of the last statement in the DO-loop) THUSLY
!IS ALWAYS THE HEAD OF THE LIST. LOCAL REFERENCE COUNTS ARE KEPT
!IN THE LREFCNT = SN1STLAB FIELD.
MAP BASE LLLNO;
PA_.TOP[DOLBL];
PA[SNEXTND]_.LOOP;
!MAKE LLLNO POINT TO THE HEAD OF THE LINK LIST WE ARE ABOUT TO
!BUILD . THE LIST IS CARRIED IN THE SNNXTLAB FIELD OF
!THE LABEL TABLE.
LLLNO_.TOP[DOLBL];
! Local label count incremented by DO plus label itself.
%1112% LLLNO[LREFCNT]_.LLLNO[LREFCNT]+2;
!NOW GET ALL THE OTHERS IN THE LOOP
!SNEXTND POINTS BACK TO THE DO DEPTH ANALYSIS FROM WHICH WE CAN
!ALWAYS GET TO THE DO STATEMENT ITSELF
P_.TOP[CLINK];
DO
BEGIN
IF .P[SRCLBL] NEQ 0 AND .P[SRCLBL] NEQ .TOP[DOLBL] THEN
BEGIN
PA_.P[SRCLBL];
LLLNO_LLLNO[SNNXTLAB]_.PA;
! Get the local reference count right.
%1125% LLLNO[LREFCNT]_.LLLNO[LREFCNT]+1;
!SET SNEXTND FIELD OF THE LABEL TABLE ENTRY
PA[SNEXTND]_.LOOP;
!ZERO THE LINK FIELD TO PREVENT LEFTOVERS
!MAKING TROUBLE
PA[SNNXTLAB]_0;
END;
!IF THIS IS A DO LOOP WE WANT TO SKIP THE LABELS
%1164% !THAT ARE DEFINED WITHIN IT.
IF .P[SRCID] EQL DOID THEN
BEGIN
P_.P[DOLBL];
%1164% P_.P[SNHDR]
END;
P_.P[CLINK]
END UNTIL .P EQL .BOTTOM;
END; ! of MAKLLL
ROUTINE MOORE=
!++
!DO FORWARD MOORE FLOOD
!--
BEGIN
EXTERNAL OPTERR;
LABEL NODOM; ![637]
!HEAD POINTS TO TOP OF GRAPH
!INITIALIZE ITS LEVEL TO 1.
!FOLLOW THE SUCCESOR CHAIN (P1 IS FOLLOWING CHAIN, P2 IS POINTING
! AT ACTUAL SUCCESSOR STATEMENT NODE).
!INITIALIZE THE LEVEL NUMBER AND PREDOMINATORE FIELDS OF EACH SUCCESSOR.
!ALSO LINK THE NODES TOGETHER IN MOORE FLOOD ORDER (TAIL IS USED FOR THIS).
HEAD[LEVEL] _1;
DO
BEGIN
P1_.HEAD[SUCPTR];
WHILE .P1[CESLNK] NEQ 0 DO
BEGIN
P2_.P1[CESSOR];
IF .P2[LEVEL] EQL 0 THEN
BEGIN
%637% IF .P2[POSTDOM] EQL 0
%637% THEN
%637% NODOM: BEGIN
%637% !WE HAVE FOUND A PART OF THE GRAPH THAT THE
%637% !COMPILER THINKS IS PART OF AN INFINITE LOOP.
%637% !ACTUALLY, THERE ARE PROBABLY EXITS LIKE
%637% !CALL EXIT OR CALL DOSTOP THAT THE COMPILER
%637% !DOES NOT RECOGNIZE AS EXITS.
%637% !WE WANT TO FIND THE "BOTTOM" OF THIS LOOP
%637% !AND MAKE IT A PREDECESSOR TO THE END STATEMENT
%637% !TO CONNECT THE GRAPH.
%637% !WE WILL DO THIS BY LOOKING FOR A STATEMENT
%637% !THAT HAS BOTH NO POSTDOMINATOR (I.E. IS IN
%637% !THE LOOP) AND NO SUCCESSOR IN THE LOOP THAT
%637% !WE HAVE NOT ALREADY LOOKED AT (I.E. HAS A LEVEL
%637% !OF ZERO).
%637% LOCAL PHAZ2 PX:PY;
%637% PX_.P2[SUCPTR];
%637% WHILE .PX[CESLNK] NEQ 0
%637% DO
%637% BEGIN
%637% PY_.PX[CESSOR];
%637% IF .PY[POSTDOM] EQL 0
%637% AND .PY[LEVEL] EQL 0
%637% THEN
%637% LEAVE NODOM;
%637% PX_.PX[CESLNK]
%637% END;
%637% DISCONFLG_TRUE;
%637% LNKFWD(.LEND,.P2);
%637% LNKREV(.P2,.LEND)
%637% END;
P2[LEVEL] _.HEAD[LEVEL] + 1;
P2[PREDOM] _ .HEAD;
TAIL[BUSY] _ .P2;
TAIL_.P2;
END;
P1_.P1[CESLNK];
END;
HEAD_.HEAD[BUSY];
END UNTIL .HEAD EQL 0;
END; ! of MOORE
ROUTINE SANDBAG=
BEGIN
!THE NAME IS IN KEEPING WITH THE FLOOD IDEA
!THE ROUTINE REINITIALIZES THE LEVEL FIELDS OF THE
!OPTIMIZERS WORDS TO TRY AGAIN ON EITHER A FORWARD OR REVERSE
!MOORE FLOOD.
! The routine SANDBAG clears the LEVEL and BUSY fields of each
! node on the BUSY list. It is called after post-dominators
! are computed to prepare for the pre-dominator algorithm.
DO
BEGIN
HEAD[LEVEL]_0; !ZERO LEVEL FOR FLOOD ALGORITHM
OLDHEAD_.HEAD[BUSY];
!ALSO ZERO BUSY FIELD SO FORWARD BUSY LIST WILL TERMINATE
HEAD[BUSY]_0;
HEAD_.OLDHEAD;
END UNTIL .HEAD EQL 0;
END; ! of SANDBAG
GLOBAL ROUTINE FLOOD=
BEGIN
MAP PHAZ2 TOP;
%637% EXTERNAL OPTERR,WARNERR;
%637% !ASSIGN MOORE FLOOD NUMBER AND SET UP BUSY LIST FOR
%637% !PREDOMINATOR ALGORITHM
%637%
%637% DO
%637% BEGIN
%637% !GET POSTDOMINATORS FIRST
%637% REFLOOD();
%637% PDOMINATE();
%637% !ZERO BUSY LIST AND LEVEL FIELDS FROM POSTDOMINATOR ALGORITHM
%637% HEAD_.OLDHEAD;
%637% SANDBAG();
%637% HEAD_.TOP; TAIL _ .TOP;
%637% HEAD[PREDOM]_.HEAD;
%637% DISCONFLG_FALSE;
%637% MOORE();
%637% !IF THE GRAPH IS DISCONNECTED, THEN MOORE WILL HAVE SET
%637% !DISCONFLG AND MADE MORE CONNECTION(S) IN THE GRAPH TO
%637% !HOPEFULLY CONNECT IT. IF SO, ZERO EVERYTHING AND START
%637% !OVER USING NEW PROGRAM GRAPH.
%637% IF .DISCONFLG THEN (HEAD_.TOP; SANDBAG())
%637% END UNTIL NOT .DISCONFLG;
%637%
%637% !IF WE DIDN'T REACH TOP AFTER ALL THAT, SOMETHING'S WRONG
%1066% IF .TOP[POSTDOM] EQL 0 THEN
%1066% BEGIN
%1066% ISN_0;
%1066% OPTERR(E37)
%1066% END;
%637%
%637% !NOW LOOP THROUGH THE PROGRAM LOOKING FOR STATEMENTS THAT WERE NOT
%637% !FOUND BY THE ABOVE MOORE FLOOD. THESE STATEMENTS ARE INACCESSIBLE
%637% !AND CAN BE DELETED.
%637% HEAD_.TOP;
%637% PREV_.TOP;
%637% WHILE .HEAD NEQ .LEND DO
%637% BEGIN
%1137% IF .HEAD[SRCOPT] NEQ 0 ! If in an inner loop, no optimizer words
%1137% AND .HEAD[LEVEL] EQL 0
%637% AND .HEAD[SRCID] NEQ ENDID !NEVER DELETE ENDS
%637% AND .HEAD[SRCID] NEQ ENTRID !NEVER DELETE ENTRIES
%637% THEN
%637% BEGIN
%637% !GENERATE A MESSAGE TO SAY THERE WAS
%637% !INACCESSIBLE CODE
%637%
%637% IF .HEAD[SRCISN] NEQ 0 THEN
%637% WARNERR(.HEAD[SRCISN],E105); !ISSUE WARNING MESSAGE
%637% !IF WE ARE REMOVING A DO MARK IT AS GONE
%637% IF .HEAD[SRCID] EQL DOID THEN
%637% BEGIN
%637% REGISTER BASE T;
%637% HEAD[DOREMOVED]_1;
%637% !WE WILL DELETE THE WHOLE LOOP
%1140% T_.HEAD[DOLBL];
%1140% DO
%1140% BEGIN
%1140% IF .HEAD[SRCID] EQL DOID THEN
%1140% IF .HEAD[HASENT] NEQ 0 ! Loop has entrances
%1140% THEN ! Inaccessible DO, but accessible labels
%1140% BEGIN
%1140% ISN_.HEAD[SRCISN];
%1140% OPTERR(E37); ! Quit. Optimizer would loop.
%1140% END;
%1140% HEAD_.HEAD[SRCLINK]
%1140% END
%1137% UNTIL .HEAD[SRCLBL] EQL .T;
%637% END;
%637% PREV[SRCLINK]_.HEAD[SRCLINK]
%637% END
ELSE
PREV_.HEAD;
HEAD_.HEAD[SRCLINK];
END; !WHILE LOOP
LEND_.PREV[SRCLINK];
HEAD_.TOP;
DOMINATE();
END; ! of FLOOD
ROUTINE DOMINATE=
BEGIN
EXTERNAL CSTMNT,ISN;
MAP BASE CSTMNT;
!FIND PREDOMINATORS IN THE FORWARD GRAPH
!THE NOCHANGE GOVERNS THE ITERANTION. IT IS INIATIALLY TRUE
!AND BECOMES FALSE WHEN NO NODES WERE UPDATED ON AN ENTIRE PASS.
!THE SUCCESSORS OF HEAD ARE EXAMINED.
!P3 FOLLOWS THE SUCCESSOR LIST. PO POINTS TO THE ACTUAL SUCCESSOR.
!THE PREDOMINATOR OF EACH SUCCESSOR IS EXAMINED. THE LEVEL (MOORE FLOOD)
!IF THE SUCCESSOR IS COMPARED WITH THE LEVEL OF THE NODE (P1, INITIALLY
! HEAD) UNDER CONSIDERATION. THE PREDOMINATOR CHAINS ARE JUGGLED
!BACKWARD UNTIL THE LEVELS ABD EQUAL. THE PREDOMINATORE OF PO IS
!CHANGED IF APPROPRIATE.
LOCAL NOCHANGE;
HEAD_.TOP;
HEAD[PREDOM]_.TOP; !STOPS IT AT TOP
DO
BEGIN
NOCHANGE _ 1;
DO
BEGIN
!CSTMNT AND ISN FOLOW THE PROCESS FOR DEBUGGING PURPOSES.
CSTMNT_.HEAD;
ISN_.CSTMNT[SRCISN];
%2366% P3 = .HEAD[SUCPTR];
WHILE .P3[CESLNK] NEQ 0 DO
BEGIN
PO_.P3[CESSOR];
P2_.PO[PREDOM];
%2366% P1 = .HEAD;
WHILE .P1 NEQ .P2 DO
IF .P1[LEVEL] LSS .P2[LEVEL] THEN
P2_.P2[PREDOM] ELSE P1_.P1[PREDOM];
IF .PO[PREDOM] NEQ .P1 THEN
BEGIN
PO[PREDOM] _ .P2;
NOCHANGE _ 0;
END;
P3_.P3[CESLNK];
END;
HEAD_.HEAD[BUSY];
END UNTIL .HEAD EQL 0;
HEAD_.TOP;
END UNTIL .NOCHANGE;
END; ! of DOMINATE
ROUTINE REFLOOD=
BEGIN
!ASSIGN MOORE FLOOD NUMBER AND SET UP BUSY LIST FOR
!POSTDOMINATOR ALGORITHM
!SEE COMMENTS IN ROUTINE MOORE FOR THE ALGORITHM. IT IS
!IDENTICAL TO THE PREDOMINATOR *FLOODING* PROCESS EXCEPT THAT
!IT IS STARTED AT LEND INSTEAD OF TOP.
!THE VARIABLES P1 AND P2 AND TAIL ALSO HAVE THE SAME FUNCTIONS.
EXTERNAL CSTMNT,ISN;
MAP BASE CSTMNT;
! LEND IS THE SUPEREXIT
HEAD_.LEND;
TAIL_.LEND;
OLDHEAD_.HEAD;
HEAD[POSTDOM]_.HEAD;
HEAD[LEVEL] _1;
DO
BEGIN
CSTMNT_.HEAD;
ISN_.CSTMNT[SRCISN];
P1_.HEAD[PREDPTR];
WHILE .P1[CESLNK] NEQ 0 DO
BEGIN
P2_.P1[CESSOR];
IF .P2[LEVEL] EQL 0 THEN
BEGIN
P2[LEVEL] _.HEAD[LEVEL] + 1;
P2[POSTDOM] _ .HEAD;
TAIL[BUSY] _ .P2;
TAIL_.P2;
END;
P1_.P1[CESLNK];
END;
HEAD_.HEAD[BUSY];
END UNTIL .HEAD EQL 0;
END; ! of REFLOOD
ROUTINE PDOMINATE=
BEGIN
!FIND POSTDOMINATORS IN THE REVERSE GRAPH
!SEE DOMINATE FOR DETAILS OF ALGORITHM. IT IS IDEBTICAL TO
!THE PREDOMINATORE ALGORITHM. THE VARIABLES PO,P1,P2 PREFORM
!THE SAME FUNCTIONS, EXCEPT THAT , OF COURSE, IT IS
!PREDECESSOR CHAINS THAT ARE FOLLOWED INSTEAD OF SUCCESSOR CHAINS
!AND THE POSTDOM FIELD THAT IS UPDATED.
EXTERNAL CSTMNT,ISN;
MAP BASE CSTMNT;
LOCAL NOCHANGE;
HEAD_.OLDHEAD;
DO
BEGIN
NOCHANGE _ 1;
DO
BEGIN
CSTMNT_.HEAD;
ISN_.CSTMNT[SRCISN];
%2366% P3 = .HEAD[PREDPTR];
WHILE .P3[CESLNK] NEQ 0 DO
BEGIN
PO_.P3[CESSOR];
P2_.PO[POSTDOM];
%2366% P1 = .HEAD;
WHILE .P1 NEQ .P2 DO
IF .P1[LEVEL] LSS .P2[LEVEL] THEN
P2_.P2[POSTDOM] ELSE P1_.P1[POSTDOM];
IF .PO[POSTDOM] NEQ .P1 THEN
BEGIN
PO[POSTDOM] _ .P2;
NOCHANGE _ 0;
END;
P3_.P3[CESLNK];
END;
HEAD_.HEAD[BUSY];
END UNTIL .HEAD EQL 0;
HEAD_.OLDHEAD;
END UNTIL .NOCHANGE;
END; ! of PDOMINATE
EXTERNAL DWP;
OWN LOOPTR;
MAP BASE LOOPTR;
OWN LUPSAV;
GLOBAL ROUTINE WALKER=
BEGIN
!GET A DO LOOP TO PROCESS
!CODE FOR FIRST TIME THROUGHT ONLY
!DWP IS A THREE VALUED FLAG.
! -1 INITIAL ENTRY. LUPSAV NOT VALID
! 0 NOT -1 OR 1
! 1 ONLY TREE ROOT FOUND LAST TIME. RETURN
! ZERO THIS TIME
MAP BASE LUPSAV;
!SHOULD WE QUIT
IF .DWP EQL 1 THEN RETURN (0)
ELSE
!IS THIS THE FIRST TIME
IF .DWP EQL -1 THEN
DWP_0
ELSE
BEGIN
!GRONK THE POINTER JUST PROCESSED
!********************************
!
!NOTE: THIS IS A DESTRUCTIVE WALK
!
!********************************
IF .LUPSAV[NEXTDO] NEQ 0 THEN
LUPSAV[NEXTDO]_0
ELSE
LUPSAV[PARLVL]_0;
END;
!NOW THE WALK PART
LUPSAV_0;
LOOPTR_.DLOOPTREE;
WHILE .LOOPTR[NEXTDO] NEQ 0 DO
BEGIN
LUPSAV_.LOOPTR;
LOOPTR_.LOOPTR[NEXTDO];
END;
WHILE .LOOPTR[PARLVL] NEQ 0 DO
BEGIN
LUPSAV_.LOOPTR;
LOOPTR_.LOOPTR[PARLVL];
WHILE .LOOPTR[NEXTDO] NEQ 0 DO
BEGIN
LUPSAV_.LOOPTR;
LOOPTR_.LOOPTR[NEXTDO];
END;
END;
IF .LUPSAV EQL 0 THEN
DWP_1
ELSE
DWP_0;
RETURN .LOOPTR
END; ! of WALKER
END
ELUDOM