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