Trailing-Edge
-
PDP-10 Archives
-
AP-D480B-SB_1978
-
graph.bli
There are 12 other files named graph.bli in the archive. Click here to see a list.
!THIS SOFTWARE IS FURNISHED UNDER A LICENSE AND MAY ONLY BE USED
! OR COPIED IN ACCORDANCE WITH THE TERMS OF SUCH LICENSE.
!COPYRIGHT (C) 1972,1977 BY DIGITAL EQUIPMENT CORPORATION
!AUTHOR NORMA ABEL/DCE/SJW
MODULE GRAPH(RESERVE(0,1,2,3),SREG=#17,VREG=#15,FREG=#16,DREGS=4)=
BEGIN
! REQUIRES FIRST, TABLES, OPTMAC/LIST
GLOBAL BIND GRAPV = 5^24 + 1^18 + 127; !VERSION DATE: 2-JUN-77
%(
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
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!
120 361 18451 FIX JUMP TO LABEL OF INNER DO LOOP
121 372 18314 FIX DOCOLLAPSE TO RETURN SPACE CORRECTLY
122 374 ----- FIX MIS-SPELLING (IOBRAHCH)
*** *** ***** START VERSION 5
123 VER5 ----- GRAPH ERR= FOR OPEN & CLOSE
124 443 QA656 WARNING + STOP OPT IF DISCOVER ILLEGAL DO
NESTING IN LNKEXTND IN HOOKUP
***** BEGIN VERSION 5A *****
125 535 21809 INNACCESSIBLE CODE WITH ZERO LINE NUMBER!
126 565 21810 EXTENDED RANGE DO LOOP IMPROPERLY GRAPHED
127 576 22798 GIVE LINE NUMBER CORRECTLY WHEN LOOP DETECTED
)%
SWITCHES NOLIST;
REQUIRE FIRST.BLI;
REQUIRE TABLES.BLI;
SWITCHES LIST;
REQUIRE OPTMAC.BLI;
EXTERNAL TOP,BOTTOM,ISN;
FORWARD ASSLOOKER;
OWN P,PA,PB,PREV,PC;
OWN PO,P1,P2,P3,HEAD,TAIL;
MAP PHAZ2 PA:PB:PC:P:PREV;
EXTERNAL TBLSEARCH,CORMAN,ASIPTR;
FORWARD LOKEXIT;
MAP BASE TOP;
EXTERNAL QQ,LOOP;
OWN OLDHEAD;
MAP PHAZ2 QQ;
EXTERNAL EXITNO;
OWN EXITLST;
OWN LLLNO,LLL,EPTR;
MAP PHAZ2 PO:P1:P2:P3:HEAD:TAIL;
OWN T,TLEND;
!TLEND IS USED TO KEEP LEND (THE END OF THE PHYSICAL PROGRAM)
!FROM SEEMING TO BE LOGICALLY DISCONNENTED FROM THE GRAPH OF THE
!PROGRAM
EXTERNAL RGRAPH,FGRAPH;
MAP PHAZ2 P:PA;
MAP PHAZ2 OLDHEAD;
EXTERNAL LEND;
!************************************
!*******************************
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;
!**********************************
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;
!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];
!**[443] LNKEXTND MACRO @3637 SJW 10-SEP-76
! 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
%[443]% IF .P EQL .PA [DOSRC]
%[443]% THEN BEGIN
%[443]% EXTERNAL CSTMNT, ISN, OPTERR, E140;
%[443]% MAP BASE CSTMNT;
%[443]% CSTMNT _ .PA [DOSRC]; !POINT TO ENCLOSING DO
%[443]% ISN _ .CSTMNT [SRCISN]; !GET STATEMENT # FOR WARNING
%[443]% OPTERR (E140); !ILLEGAL DO NESTING - OPT DISCONTINUED
%[443]% 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
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;
ROUTINE ABSGOCHK=
BEGIN
!UNDER NO CIRCUMSTANCES CAN THE GRAPH BE DISCONNECTED
!THIS MEANS THAT STATEMENTS THAT FOLLOW AN ABSOLUTE
!BRANCH THAT ARE UNLABELED MUST BE ELIMINATED. WE
!MUST BE CAREFUL WITH THE STOP END AND RETURN END
!COMBINATIONS, HOWEVER, SINCE WE MUST NOT ELIMINATE THE
!END STATEMENT.
!MODULE OWN P POINTS TO THE ABSOLUTE BRANCH STATEMENT.
EXTERNAL WARNERR,ISN;
LOCAL BASE LABLE;
IF .P[SRCLINK] EQL 0 THEN RETURN;
PC_.P[SRCLINK];
IF .PC[SRCLBL] EQL 0 THEN
BEGIN
IF .PC[SRCID] EQL ENDID THEN RETURN;
IF .PC[SRCID] EQL ENTRID THEN RETURN;
!OTHERWISE, THROW IT OUT
DO
BEGIN
!GENERATE A MESSAGE TO SAY THERE WAS
!INACCESSIBLE CODE
!**;[535], ABSGOCHK @3731, DCE, 18-FEB-77
!**;[535], IF LINE HAS ZERO LINE NUMBER, DO NOT PRINT WARNING -
!**;[535], PROBABLY AN OPTIMIZER CREATED STATEMENT!
%[535]% IF .PC[SRCISN] NEQ 0 THEN
WARNERR(.PC[SRCISN],E105); !ISSUE WARNING MESSAGE
!IF WE ARE REMOVING A DO MARK IT AS GONE
IF .PC[SRCID] EQL DOID THEN
BEGIN
REGISTER BASE T;
PC[DOREMOVED]_1;
!WE WILL DELETE THE WHOLE LOOP
T_.PC[DOLBL];
DO
PC_.PC[SRCLINK]
UNTIL .PC[SRCLBL] EQL .T;
END;
PC_.PC[SRCLINK];
END UNTIL .PC[SRCLBL] NEQ 0 OR .PC[SRCID] EQL ENDID
!**;[330],ABSGOCHK @ 3685,(3680 IN 4(210)),DCE,5-NOV-1975
%[330]% OR .PC[SRCID] EQL ENTRID;
!FILL IT INTO P
P[SRCLINK]_.PC;
END;
END;
ROUTINE GRAPH=
BEGIN
!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.
MACRO INFLOOP=
IF .PA EQL .P[SRCLBL] THEN OPTERR(E100)$;
EXTERNAL ENTRY,OPTERR,LOOP,LEND;
IF .PREV NEQ 0 THEN
BEGIN
!MAKE THE ABSOLUTE TRANSFER FOLLOWER CATCH UP
!BY SETTING TO0 TO INDICATE
!THAT THERE IS REALLY MORE HERE.
TLEND_0;
LNKREV(.PREV,.P); LNKFWD(.P,.PREV);
END;
SELECT .P[SRCID] OF NSET
GOTOID:BEGIN !UNCONDITIONAL GO TO
PA_.P[GOTOLBL];
INFLOOP;
HOOKUP(.PA);
PREV_0;
IF .P[SRCLINK] NEQ 0 THEN TLEND_.P;
ABSGOCHK();
END;
CGOID: 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
AGOID: BEGIN !ASSIGNED GO TO
ENTRY_.P[SRCISN];
!**;[333],GRAPH @3738 (3733 IN 4(210)),DCE,18-NOV-1975
!**;[333] IN AGOID: TURN OFF GLOBAL REGISTER ALLOCATION
![333] FOR THIS LOOP ONLY.
%[333]% 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;
IF .P[SRCLINK] NEQ 0 THEN TLEND_.P;
ABSGOCHK();
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
IFLID: BEGIN !LOGICAL IF
!ONLY TRICKY CASE
!FIRST ET 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;
IFAID: BEGIN !ARITHMETIC IF
PA_.P[AIFLESS];
INFLOOP;
HOOKUP(.PA);
PA_.P[AIFEQL];
INFLOOP;
HOOKUP(.PA);
PA_.P[AIFGTR];
INFLOOP;
HOOKUP(.PA);
PREV_0; TLEND_.P;
ABSGOCHK();
END; !ARITHMETIC IF
WRITID: BEGIN
!**;[374], GRAPH @3828, DCE, 22-APR-76
!**;[374], FIX MIS-SPELLING OF MACRO NAME!
%[374]% IOBRANCH;
PREV_.P;
END;
READID: BEGIN
IOBRANCH;
PREV_.P;
END;
CALLID: BEGIN !CALL STATEMENT
!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 STATEMENT
DOID: BEGIN !DO STATEMENT
!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
PA_.PC[LEFTP];
HOOKUP(.PA);
!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;
RETUID: BEGIN !RETURN STATEMENT
LNKBOT;
PREV_0; TLEND_.P;
TOP[HASRTRN]_1;
ABSGOCHK();
END;
STOPID: BEGIN !STOP STATEMENT
LNKBOT;
PREV_0;TLEND_.P;
ABSGOCHK();
END;
ENTRID: 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;
OPENID: BEGIN %[V5]%
%[V5]% IOBRANCH;
%[V5]% PREV _ .P;
%[V5]% END;
CLOSID: BEGIN %[V5]%
%[V5]% IOBRANCH;
%[V5]% PREV _ .P;
%[V5]% END;
OTHERWISE: PREV_.P;
TESN; !END OF SELECT
!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];
IF .PA[SNEXTND] NEQ 0 AND
.PA[SNEXTND] NEQ .LOOP AND
.PA[SNREFNO] NEQ 1 THEN
LNKEXTND;
END;
END;
FORWARD LOKENTRANCE,MAKLLL;
GLOBAL ROUTINE GPHBLD =
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;
MAP BASE TOP:T:CSTMNT:TLEND:LEND;
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;
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;
TLEND_0;
P_.TOP[SRCLINK];
EXITNO_0; !INITIALIZE EXITNO
EPTR_0;
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
IF .LOOP NEQ 0 AND .EXITNO NEQ 0 THEN
BEGIN
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;
!TRY TO KEEP THE GRAPH FROM BEING DISCONNECTED. IF TLEND
!WAS SET AND THERE IS NOTHING CONNECTED TO LEND MAKE LEND
!BE TLEND. AS AN EXTRA CHECK FOR THIS TO BE 1000% VALID
!THE SRCLINK FIELD OF TLEND SHOULD BE LEND. THIS IS
!THE SITUATION THAT THERE IS AN ABSOLUTE BRANCH IN FRONT OF
!LEND
IF .TLEND NEQ 0 AND .TLEND[SRCLINK] EQL .LEND THEN
BEGIN
MAP PHAZ2 LEND;
P_.LEND[PREDPTR];
IF .P[CESSOR] EQL 0 THEN
LEND_.TLEND;
END;
END; !GRAPHBUILDER ROUTINE
ROUTINE ASSLOOKER(VAR)=
!*****
!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;
GLOBAL ROUTINE DOCOLLAPSE=
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.
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]);
!**;[372], DOCOLLAPSE @4191, DCE, 15-APR-76
!**;[372], DO NOT ALLOW ASSIGNED GO TO LISTS TO BE GIVEN
!**;[372], BACK BY MORE THAN ONE DO LOOP! CLEAN UP TOO.
%[372]%
%[372]% P[SRCOPT]_0;
%[372]% !CHECK FOR ASSIGNED GO TO STATEMENTS AND
%[372]% !LOGICAL IF STATEMENTS WHERE WE CAN CLEAN HOUSE
%[372]%
%[372]% ! FOR AN ASSIGNED GO TO STATEMENT, DELETE THE
%[372]% ! OPTIMIZER BUILT LIST
%[372]% IF .P[SRCID] EQL AGOID AND .P[NOLBLLST] THEN
%[372]% BEGIN
%[372]% SAVSPACE(.P[GOTONUM]-1,.P[GOTOLIST]);
%[372]% P[GOTONUM]_P[GOTOLIST]_0;
%[372]% END
%[372]% ELSE
%[372]% IF .P[SRCID] EQL IFLID THEN
%[372]% BEGIN
%[372]% PC_.P[LIFSTATE];
%[372]% IF .PC[SRCOPT] NEQ 0 THEN
%[372]% BEGIN
%[372]% RELSGRAPHELM(PC);
%[372]% SAVSPACE(4,.PC[SRCOPT]);
%[372]% PC[SRCOPT]_0;
%[372]% IF .PC[SRCID] EQL AGOID AND
%[372]% .PC[NOLBLLST] THEN
%[372]% BEGIN
%[372]% SAVSPACE(.PC[GOTONUM]-1,
%[372]% .PC[GOTOLIST]);
%[372]% PC[GOTONUM]_PC[GOTOLIST]_0;
%[372]% END
%[372]% END
%[372]% END
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;
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
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
!**;[565], LOKENTRANCE @4365, DCE, 2-MAY-77
!**;[565], PUT THIS STATEMENT ON THE SUCCESSOR LIST FOR THE TOP OF
!**;[565], THE LIST - NAMELY THE DO STATEMENT.
%[565]% LNKFWD(.PB,.TOP);
LNKREV(.TOP,.PB);
!SET FLAG FOR GLOBAL ALLOCATOR USE
TOP[HASENT]_1;
END;
END;
!ZERO THE FIELDS
PB_.PA[SNNXTLAB]; !SAVE POINTER
PA[SNNXTLAB]_0;
PA[LREFCNT]_0;
!RESTORE POINTER
PA_.PB;
END;
END;
ROUTINE LOKEXIT (LABLE)=
BEGIN
EXTERNAL OPTERR,LOOP;
!SEARCH LLL FOR LABEL
!IF NOT THERE IT IS A LOOP EXIT
!ADD TO LOOP EXIT LIST
!LABEL IS DELIBERATELY MISSPELLED
MAP BASE LLLNO:EXITLST;
LABEL WHLEXT;
MAP PEXPRNODE LABLE;
!POINT TO TOP OF LINKED LIST OF LOCAL LABELS.
LLLNO_.TOP[DOLBL];
WHILE .LLLNO NEQ 0 DO
BEGIN
IF .LLLNO EQL .LABLE THEN
BEGIN
LLLNO[LREFCNT]_.LLLNO[LREFCNT]+1;
RETURN 0;
END;
LLLNO_.LLLNO[SNNXTLAB];
END;
!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;
ROUTINE MAKLLL=
BEGIN
!CREATE A LINKED LIST OF THE LOCAL LABELS IN THIS INTERVAL.
!THE LINKS ARE KEPT IN THE SNNXTLAB FIELD OF THE LABEL
!TABLE. TOP[DOLBL] 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];
!INITIALIZE THE FIELDS
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;
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
!THAT ARE DEFINED WITHIN IT. BUT WE WANT TO
!UPDATE THE SNEXTND FIELD OF THE LABEL TABLE ENTRIES
!FOR THEM TO POINT TO THE OUTER-MORE LOOP WE ARE
!NOW PROCESSING. ALSO BE CAREFUL THAT THIS IS NOT
!THE MAIN PROGRAM.
IF .P[SRCID] EQL DOID THEN
BEGIN
PB_.P[DOLBL];
!UNTIL WE ARE OUT OF THIS INNER MORE LOOP
WHILE .P[SRCLBL] NEQ .PB DO
BEGIN
IF .P[SRCLBL] NEQ 0 AND .LOOP NEQ 0 THEN
BEGIN
!GET THE LABEL TABLE POINTER
PA_.P[SRCLBL];
PA[SNEXTND]_.LOOP;
END;
!LOOK AT NEXT ENTRY
P_.P[SRCLINK];
END;
!**;[361], MAKLLL @4432, DCE, 26-MAR-76
!**;[361], INCLUDE THE LABEL TERMINATING THE LOOP!
%[361]% PA_.P[SRCLBL];
%[361]% PA[SNEXTND]_.LOOP;
END;
P_.P[CLINK]
END UNTIL .P EQL .BOTTOM;
END;
FORWARD DOMINATE,REFLOOD,PDOMINATE;
ROUTINE MOORE=
BEGIN
!**;[327],MOORE @ 4440,(4435 IN 4(210)),DCE,3-NOV-1975
EXTERNAL OPTERR; %[327]%
!DO FORWARD MOORE FLOOD
!HEAD POINTS TO TOP OF GRAPH
!INITIALIZE ITS LEVEL TO 1.
!FOLLOW THE SUCCESORE 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
!**;[327],MOORE @ 4456,(4451 IN 4(210)),DCE,3-NOV-1975
%[327] CHECK FOR POSTDOMINATORS BEING ASSIGNED TO
[327] ALL NODES REACHABLE FROM THE ENTRY.
[327] AN EXAMPLE PROGRAM THAT WILL CAUSE THEM
[327] TO BE NOT ASSIGNED IS:
[327] IF (EXPR) GO TO 10
[327] 5 CALL FN(X)
[327] X2 = X*7
[327] GO TO 5
[327] 10 STOP
[327] END
[327] STATEMENTS BETWEEN 5 AND GO TO 5 WILL NOT BE
[327] ASSIGNED POSTDOMINATORS BECAUSE THEY CANNOT BE
[327] REACHED FROM THE END OF THE PROGRAM (FN
[327] PRESUMABLY WILL EXIT SOMETIME!)%
!**;[576], MOORE @4565, DCE, 2-JUN-77
!**;[576], PICK UP THE LINE NUMBER WHEN THE LOOP IS DETECTED.
!**;[576], THIS MAY OR MAY NOT BE USEFUL IN ISOLATING THE LOOP.
%[576]% IF .P2[POSTDOM] EQL 0
%[576]% THEN (ISN_.P2[SRCISN]; OPTERR(E100));
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;
!***********************************************
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.
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;
!*****************************************************
GLOBAL ROUTINE FLOOD =
BEGIN
MAP PHAZ2 TOP;
EXTERNAL OPTERR;
!ASSIGN MOORE FLOOD NUMBER AND SET UP BUSY LIST FOR
!PREDOMINATOR ALGORITHM
!GET POSTDOMINATORS FIRST
REFLOOD();
PDOMINATE();
!ZERO BUSY LIST AND LEVEL FIELDS FROM POSTDOMINATOR ALGORITHM
HEAD_.OLDHEAD;
SANDBAG();
HEAD_.TOP; TAIL _ .TOP;
HEAD[PREDOM]_.HEAD;
MOORE();
!WAIT ONE MINUTE. BEFORE PLUNGING AHEAD GIVE A CHECK
!ON THE CONNECTIVITY OF THE GRAPH. SOME PROGRAMS JUST
!ARE NOT CONNECTED AND WE SHOULD FIND OUT NOW RATHER THAN
!LATER
IF .TOP[POSTDOM] EQL 0 THEN
BEGIN
!THIS IMPLIES THAT WE WERE UNABLE TO GET THE POSTDOMINATORS
!ALL THE WAY TO THE FRONT OF THE BUS.
!SO WE WILL TRY TO ELIMINATE STATEMENTS NOT REACHABLE
!FROM THE ENTRY
HEAD_.TOP;
PREV_.TOP;
!NOT REACHABLE MEANS IT DIDNT GET A LEVEL NUMBER IN THE FORWARD
!MOORE FLOOD WE JUST DID
WHILE .HEAD NEQ .LEND DO
BEGIN
IF .HEAD[LEVEL] EQL 0 THEN
PREV[SRCLINK]_.HEAD[SRCLINK]
ELSE
PREV_.HEAD;
HEAD_.HEAD[SRCLINK];
END; !WHILE LOOP
LEND_.PREV[SRCLINK];
HEAD_.TOP;
!NOW TRY TO GET POSTDOMINATORS AGAIN
SANDBAG(); !ZERO FIELDS
REFLOOD();
PDOMINATE();
!IF WE STILL DIDNIT MAKE IT GIVE UP
IF .TOP[POSTDOM] EQL 0 THEN OPTERR(E37);
!IF WE ARE NOT QUITTING THEN GET THOSE FORWARD FLOOD
!NEMBERS BACK
HEAD_.OLDHEAD;
!FIRST REINITIALIZE THE FIELD
SANDBAG();
HEAD_TAIL_.TOP;
MOORE();
END;
DOMINATE();
END;
!*********************************************
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];
P1_.HEAD;
P3_.P1[SUCPTR];
WHILE .P3[CESLNK] NEQ 0 DO
BEGIN
PO_.P3[CESSOR];
P2_.PO[PREDOM];
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;
!***********************************************************
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;
!******************************************************
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];
P1_.HEAD;
P3_.P1[PREDPTR];
WHILE .P3[CESLNK] NEQ 0 DO
BEGIN
PO_.P3[CESSOR];
P2_.PO[POSTDOM];
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;
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;
END
ELUDOM