! File: TNBIND.BLI ! ! This work was supported by the Advanced Research ! Projects Agency of the Office of the Secretary of ! Defense (F44620-73-C-0074) and is monitored by the ! Air Force Office of Scientific Research. MODULE TNBIND(TIMER=EXTERNAL(SIX12))= BEGIN ! ! ! ! ! TNBIND MODULE ! ---------------- ! ! ! AUGUST 1972 ! BILL WULF ! RICHARD JOHNSSON ! ! LATER ADDITIONS ! PAUL KNUEVEN ! BRUCE LEVERETT ! ! ! THIS MODULE ASSIGN SYMBOLIC 'TEMPORARY NAMES' TO HOLD THE ! RESULTS OF EXPRESSIONS - THEN BINDS THESE NAMES TO REGISTERS ! AND/OR MEMORY LOCATIONS. THE MODULE CONSISTS OF THREE ! DISTINCT SEQUENTIALLY EXECUTED PHASES: TN-ASSIGNMENT, RANKING, ! AND PACKING. ! ! ASSIGNMENT: IN THIS PHASE A TREE-WALK (IN EXECUTION ORDER) ! IS MADE. A SEPARATE ROUTINE IS CALLED FOR EACH TYPE OF ! NODE (+,*,IF, ETC.). GENERALLY THE FUNCTIONS OF THESE ROUTINES ! ARE TO: ! 1) ASSIGN TEMP-NAMES AND/OR LABELS IN SUCH A WAY ! THAT ,IF POSSIBLE, THE SAME NAME ! IS USED FOR THE ENTIRE EVALUATION OF AN EXPRESSION. ! AN ATTEMPT IS MADE TO 'TARGET' THE VALUES OF SOME ! (SEVERAL) EXPRESSIONS TO THE SAME NAME. ! 2) COMPUTE THE RELATIVE 'IMPORTANCE' OF A PARTICULAR ! TEMP-NAME BY EXAMINING THE WAY AND NUMBER OF ! TIMES IT IS USED. ! 3) DETERMINE THE 'LIFE' OF A TEMP NAME -- THAT IS, THE ! SPAN OF PROGRAM OVER WHICH THE NAME MUST OCCUPY ! A SINGLE LOCATION. ! ! RANKING: USING THE 'IMPORTANCE' MEASURE COMPUTED IN THE FIRST ! PHASE, THE RANKING PHASE ORDERS THE TEMP-NAMES SO THAT THE ! PACKING PHASE MAY ALLOCATE THE MOST IMPORTANT FIRST. ! THIS INSURES THAT THE MOST IMPORTANT TEMP-NAMES WILL BE BOUND ! TO THE MOST DESIRABLE LOCATIONS -- GENERALLY REGISTERS. ! ! PACKING: THE FINAL PHASE PROCESSES TEMP-NAMES IN THE ORDER ! DEFINED BY THE RANKING PHASE. USING THE 'LIFE-SPAN' INFORMATION ! THIS PHASE ATTEMPTS TO 'FIT' OR 'PACK' THE TEMP-NAMES INTO ! THE VARIOUS POSSIBLE LOCATIONS. ROUGHLY, THE ORDER OF PREFERENCE ! FOR VARIOUS LOCATIONS IS: ! ! 1) AN 'OPEN' REGISTER -- THIS IS A REGISTER WHICH HAS ALREADY ! BEEN USED (AND THUS ITS CONTENTS NEED NOT BE SAVED). ! 2) AN 'OPEN LOCAL' -- AT LEAST IF THE COST OF USING ! A LOCAL FOR THIS TEMP IS LESS THAN OPENING A NEW ! REGISTER. ! 3) A 'CLOSED REGISTER' ! 4) AN 'OPEN LOCAL' ! 5) A 'CLOSED LOCAL'. ! ! ! THIS BRIEF DESCRIPTION HARDLY DOES JUSTICE TO THE ALGORITHMS, ! BUT IT SHOULD GIVE AN OVERVIEW OF WHATS GOING ON. DETAILS ! WILL BE FOUND BELOW. ALSO, NOTE THE OUTLINE OF THE ORGANIZATION ! OF THE CODE GIVEN BELOW! ! ! ! ! ! SWITCHES NOLIST; REQUIRE COMMON.BEG; REQUIRE PREDEF.BEG; REQUIRE GTST.BEG; REQUIRE ST.BEG; REQUIRE GTX.BEG; REQUIRE FLOW.BEG; REQUIRE LDSF.BEG; SWITCHES LIST; REQUIRE DTC.BEG; REQUIRE TN.BEG; BEGIN REQUIRE TRY.BEG; ! OUTLINE OF THE TNBIND MODULE !------------------------------ ! ! ! ! I. - GENERAL UTILITIES FOR TNBIND ! A. - FOR MANIPULATING STACKS OF LISTS ! B. - FOR ACCESSING TN REPRESENTATIVES ! C. - FOR PERFORMING AN ACTION ON A LIST OF TN'S ! D. - ROUTINES FROM THE LOWSEGMENT ! E. - MISCELLANEOUS ! II. - TEMP NAME AND LABEL ASSIGNMENT ! A. - UTILITIES ! B. - SPECIFIC ROUTINES ! C. - DRIVER FOR TEMP NAME/LABEL ASSIGNMENT ! III. - RANKING TEMP NAMES ! A. - UTILITIES ! B. - SORTING OF TEMP NAMES ! C. - DRIVER FOR RANKING ! IV. - PACKING ! A. - UTILITIES ! 1. - PREFERENCES ! 2. - FITTING ! ! 3. - OPENING ! ! B. - REGISTERS ! FOR THESE FIVE, SEE TRY.BLI ! C. - STATIC TEMPS ! ! D. - DYNAMIC TEMPS ! ! E. - DRIVER FOR PACKING ! F. - MARKING OF TNS AFTER PACKING ! V. - DRIVER FOR TNBIND MODULE ! EXTERNALS, FORWARDS, AND BINDS ! ------------------------------------------------- EXTERNAL ! TNREP, ! FROM LOW SEGMENT RELTNREPLST, ! FROM LOW SEGMENT GETTN, ! FROM LOW SEGMENT DELINK, ! FROM LSTPKG PULSELIST, ! FROM LSTPKG EQLPOSSIZE, ! FROM DELAY TRYFIT, ! THE NEXT FEW ARE FROM TRY.BLI OPENLIST, CLOSELIST, REOPEN, ISREGLST, TRYSPREG, TRYOPREG, TRYCLREG, TRYOPSTEMPS, TRYCLSTEMPS, TRYSPDYTEMP, OPENDYTEMP, CLOSEDYTEMPS, TRYDYTEMPS, MUSTBETOP, ! LON, ! LINEAR ORDER NUMBER ! FON, ! FLOW ORDER NUMBER MAXLOCALS, ! NUMBER OF LOCALS IN 'MAXLOCALS' AREA STATICSIZE, ! NUMBER OF LOCALS IN 'STATIC LOCALS' AREA ! SRLST, ! HEAD OF SPECIFIC REGISTER LIST ! ARLST, ! HEAD OF ANY REGISTER LIST ! SLLST, ! HEAD OF SPECIFIC LOCAL LIST ULST, ! BASE OF VECTOR OF "USUAL" LISTS ! LOOPDEPTH, ! CURRENT LOOPDEPTH MAXKOST, ! MAXIMUM VALUE OF XUSECOMPLEXITY FIELD MAXFONSPAN, ! MAX FONLU-FONFU CALLSTK, ! BASE OF STACK OF TN'S IN CALLS ! LOOPSTK, ! BASE OF STACK FOR TN'S IN LOOPS FONSTK, ! STACK OF FON VALUES AT CONTROL NODES LOOPLFSTK, ! STACK OF LOOP BEGINNING LON/FON VALUES DTDSTK; ! STACK OF DY-TEMP-DEPTH AT CONTROL NODES ! PREFLST; ! HEAD OF PREFERENCE LIST ! STEMPS, ! HEAD OF LIST OF STATIC TEMPS ! DTEMPS, ! HEAD OF LIST OF DYNAMIC TEMPS ! REGS, ! HEAD OF REGISTER LIST ! TNCHAIN; ! HEAD OF LIST OF ALL TEMP NAMES BIND ESTIM=FONSTK; ! RE-USE OF GLOBAL BIND ULSZ=4, ! SIZE OF USUAL LIST VECTOR VREGNUM=0, ! NUMBER OF THE VALUE REGISTER MAGIC3=3, ! CAN "IF" RESULT REG BE USED AS TARGET? MAGIC2=5; ! IS TOS OK FOR TARGET? ! I. - GENERAL UTILITIES FOR TNBIND ! ------------------------------------------------ ! A. - FOR MANIPULATING STACKS OF LISTS ! ------------------------------------------------ ! ! THE FOLLOWING STRUCTURES/MACROS/AND ROUTINES DEFINE ! A SYSTEM OF STACKS OF LISTS -- THAT IS, EACK STACK ! ELEMENT IS THE HEADER OF A DOUBLY LINKED CIRCULAR ! LIST. THESE STACKS ARE USED, IN GENERAL, WHERE SEVERAL ! PIECES OF INFORMATION MUST BE RECORDED AT A SINGLE ! LEVEL OF (OBJECT PROGRAM) CONTROL. THE TYPICAL ENTRIES ! ARE 'TN-REPRESENTATIVES' -- TWO WORD CELLS WHICH ! POINT TO A TN CELL. ! ! STRUCTURE LSTSTK[I,J,K,L]= [I+1] CASE .I OF SET (.LSTSTK + .J - 1)<0,36>; (.LSTSTK+2+@.LSTSTK)<.K,.L>; .(.(.LSTSTK+2+@.LSTSTK)<0,18>)<.K,.L>; .(.(.LSTSTK+2+@.LSTSTK)<18,18>)<.K,.L>; (.LSTSTK+1+.J)<.K,.L> TES; MAP PLSTSTK CALLSTK; STRUCTURE LLSTSTK[I,J,K,L]= CASE .I OF SET (.LLSTSTK + .J)<.K,.L>; GT[.(.LLSTSTK)<0,18>,.J,.K,.L]; GT[.(.LLSTSTK)<18,18>,.J,.K,.L]; TES; MACRO ADDTOTOS(STK,Z)=BEGIN MAP PLSTSTK STK; LINK((Z),STK[TOS]) END$; MACRO INITSTK(STK)= BEGIN MAP PLSTSTK STK; STK_GETSPACE(GT,STKSIZE+2); STK[CURD]_-1; STK[MAXD]_-1 END$; ! B. - FOR ACCESSING TN REPRESENTATIVES ! ------------------------------------------------ ! ! ! THIS SECTION DEFINES ACCESSING OF 'TN-REPRESENTATIVES'. ! IN THE PROCESS OF TNBINDING IT IS NECESSARY TO ! INCLUDE THE TN'S ON SEVERAL LISTS SIMULTANEOUSLY. ! RATHER THAN ALLOW SPACE IN THE TN-CELL FOR ALL POSSIBLE ! SUCH LINKINGS, A 'REPRESENTATIVE' OF THE TN-CELL IS ! PLACED ON THE APPROPRIATE LISTS. THE STRUCTURE OF ! TN-REPS IS DEFINED SO THAT FIELDS IN THE TNCELL MAY ! BE ACCESSED ,BY NAME, INDIRECTLY. ! ! MACRO RELTNREP(A)=RELEASESPACE(GT,(A),2)$; ! C. - FOR PERFORMING AN ACTION ON A LIST OF TN'S ! ------------------------------------------------ ! ! ! D. - ROUTINES FROM THE LOWSEGMENT ! ------------------------------------------------ %%%< ROUTINE TNREP(TN)= BEGIN LOCAL TNREPR T; T_GETSPACE(GT,2); T[TNPTR]_.TN; T[RLINK]_T[LLINK]_.T END; ROUTINE RELTNREPLST(LST)= BEGIN MAP TNLSTHDR LST; UNTIL EMPTY(.LST) DO RELEASESPACE(GT,DELINK(.LST[RLINK]),2) END; BIND TNSIZE=6; ! SIZE OF TEMP NAME CELL ROUTINE GETTN= BEGIN LOCAL GTVEC T; T_GETSPACE(GT,TNSIZE); T[TYPEF]_TEMPNAMET; T[LONFU]_T[FONFU]_-1; LINK(TNREP(.T),TNCHAIN); .T END; >%%% ! E. - MISCELLANEOUS ! ------------------------------------------------ FORWARD TLA,WANTPREF; EXTERNAL FIXLIST; STRUCTURE TNWORD[I,J]=.TNWORD<.I,.J>; MACRO CONTINUE=EXITBLOCK$, DUMMYBLOCK=BIND ZQZQZQZQ=437$, FILLTX=(IF .TX EQL 0 THEN TX_GETTN())$, ISRELOP(NODE)=ONEOF(.GT[.NODE,NODEX], (BMSKX(SGTROP,6) OR BMSKX(SGTRUOP,6) OR BMSK(SBITOP)))$, ISDESTROYABLE(LEX)=(BIND LEXEME QQ=LEX; .QQ[IDTF])$, LASTOPERAND=OPERAND(.NODE[NODESIZEF]-1)$, LOG2(N)=(REGISTER QQ; IF (QQ_FIRSTONE(N)) GTR 0 THEN 36-.QQ ELSE 0)$, MIN(A,B)=(IF (A) LSS (B) THEN (A) ELSE (B))$, RESREQ=(.NODE[NSRFF] NEQ RFNONE)$; ! F. STRUCTURE/MACROS/ROUTINES FOR LIST-IMPLEMENTED STACKS ! ------------------------------------------------ STRUCTURE LSTACK[I,J,K,L]= CASE .I OF SET (.LSTACK)<0,36>; (.LSTACK + .J)<.K,.L>; (.(.LSTACK)<0,18>+.J)<.K,.L> TES; MAP LSTACK FONSTK:LOOPLFSTK:DTDSTK; MACRO SWRD= 2,1,0,36$, MFON= 2,1,18,18$, ! MAXIMUM FON LFON= 2,1,0,18$, ! LAST FON LEFON= 2,1,0,18$, ! LEAST FON LELON= 2,1,18,18$, ! LEAST LON LDTD= 2,1,0,36$, ! LAST DYTEMPS DEPTH MDTD=2,2,0,36$; ! MINIMUM DYTEMPS DEPTH MACRO PUSHLS(STK,ZVAL)= BEGIN REGISTER ITEM ZQ; ZQ_GETSPACE(GT,3); ZQ[LLINK]_ZQ[RLINK]_.ZQ[BASE]; LINK(.ZQ,STK); STK[SWRD]_ZVAL END$, POPLS(STK)= RELEASESPACE(GT,DELINK(.STK[RLINK]),3)$, INITLS(STK)=NULLLST(STK)$; ! II. - TEMP NAME AND LABEL ASSIGNMENT ! ------------------------------------------------ ! ! ! THIS SECTION CONTAINS THE CODE TO DO PHASE 1: ASSIGNMENT ! OF TEMP NAMES AND LABELS. SEE BELOW FOR DETAILS. ! ! ! A. - UTILITIES ! ------------------------------------------------ ! COST COMPUTATIONS: THESE UTILITIES DEFINE THE COST OF ! USING A PARTICULAR TEMP NAME. TWO COSTS ARE COMPUTED: ! 1) A 'MAX' COST -- WHICH RESULTS IF THE TEMP WERE ! ASSIGNED TO A MEMORY LOCATION, AND 2) A 'MIN' COST ! -- WHICH RESULTS IF A REGISTER IS USED. IN BOTH CASES ! THE COST IS A FUNCTION OF THE OPERATOR, TYPE OF USE, AND CURRENT LOOPDEPTH. ! ! STRUCTURE CONSTVECTOR[I]=.CONSTVECTOR<0,36>; BIND VECTOR KOPND=PLIT(0,1,1,2,1,2,2,3); ! INDEXED BY ADDRESSING MODES 0-7 BIND VECTOR KOPNDX=PLIT(1,2,7,9,7,9,7,8); COMMENT ! UPDATE ! ! FUNCTION: ! INCREMENT THE MIN AND MAX USE COMPLEXITY FIELDS OF THE TEMP NAME ! POINTED TO BY 'NODE' (A GT NODE OR SYMBOL TABLE ENTRY) BY 'MN' & 'MX' ! RESPECTIVELY. ALSO UPDATE 'MAXKOST' IF ANY LARGER ONE COMES THRU. ! ROUTINE UPDATE(NODE,MN,MX)= BEGIN MAP GTVEC NODE; BIND LEXEME LEX=NODE; LOCAL GTVEC TN; IF .LEX[LTYPF] NEQ LITTYP THEN IF (TN_.NODE[REGF]) GEQ 8 THEN IF .TN[TYPEF] EQL TEMPNAMET THEN IF NOT .TN[TNLITBIT] THEN BEGIN LOCAL GTVEC Z; Z_.TN[REGF]; IF .Z GEQ 8 THEN ! TAKING ACCOUNT OF BINDSTORE (IF .Z[TYPEF] EQL TEMPNAMET THEN RETURN UPDATE(.TN,.MN,.MX) ELSE RETURN UPDATE(.Z,.MN,.MX) ); TN[USECOMPLEXITY]_.TN[USECOMPLEXITY]+.MN*(.LOOPDEPTH+1); Z_TN[XUSECOMPLEXITY]_.TN[XUSECOMPLEXITY]+.MX*(.LOOPDEPTH+1); IF .Z GTR .MAXKOST THEN MAXKOST_.Z END END; COMMENT ! K ! ! FUNCTION: ! COST OF ACCESSING NODE 'N' IF IT'S IN A REGISTER. ! MACRO K(N)=(MAP GTVEC N; BIND LEXEME LN=N; IF .LN[LTYPF] EQL LITTYP THEN 1 ELSE .KOPND[.N[MODE]])$; COMMENT ! KX ! ! FUNCTION: ! COST OF ACCESSING NODE 'N' IF IT'S IN MEMORY. ! MACRO KX(N)=(MAP GTVEC N; BIND LEXEME LN=N; IF .LN[LTYPF] EQL LITTYP THEN 1 ELSE .KOPNDX[.N[MODE]])$; MACRO CLITVALUE(OP)=(BIND LEXEME LOP=OP;IF .LOP[LTYPF] EQL LITTYP THEN LITVALUE(.LOP) ELSE .OP[OFFSETF])$; COMMENT ! SHIFTKOST ! ! FUNCTION: ! COMPUTE THE APPROXIMATE NUMBER OF ACCESSES TO A WORD ! REQUIRED TO SHIFT A FIELD OF SIZE 'SIZE' A DISTANCE ! OF 'DIST' BITS. ! ROUTINE SHIFTKOST(DIST,SIZE)= BEGIN DIST_ ABS(.DIST); IF .DIST GTR 12 THEN DIST_17-.DIST; IF .DIST GTR 7 THEN DIST_.DIST-7; IF .SIZE EQL 1 THEN DIST_2; .DIST END; COMMENT ! KOSTOFTEMP ! ! FUNCTION: ! COMPUTE THE NUMBER OF ACCESSES TO A WORD REQUIRED TO MAKE IT ! DESTROYABLE AND/OR SHIFT THE REQUIRED FIELD TO THE RIGHT END ! OF THE WORD. ! ROUTINE KOSTOFTEMP(NODE)= BEGIN LOCAL Z; MAP GTVEC NODE; BIND LEXEME LEX=NODE; IF .LEX[LTYPF] NEQ GTTYP THEN RETURN; Z_1 - ISDESTROYABLE(NODE); IF NOT .Z THEN IF .NODE[SIZEF] NEQ 16 THEN Z_.Z+1+SHIFTKOST(-.NODE[POSF],.NODE[SIZEF]); .Z END; COMMENT ! KKMOV ! ! FUNCTION: ! COMPUTE THE NUMBER OF ACCESSES TO 'NODE2' REQUIRED ! TO GENERATE A MOVE FROM 'NODE1' TO 'NODE2'. ! ROUTINE KKMOV(NODE1,NODE2)= BEGIN MAP GTVEC NODE1:NODE2; BIND LEXEME LEX=NODE1:LEX2=NODE2; IF .LEX2[LTYPF] EQL LITTYP THEN 1 ELSE IF .LEX[LTYPF] NEQ GTTYP THEN 1 ELSE (.NODE1[REGF] NEQ .NODE2[REGF])+ SHIFTKOST(.NODE2[POSF]-.NODE1[POSF],.NODE1[SIZEF])+ (.NODE2[SIZEF] NEQ 16) END; COMMENT ! KUNOP ! ! FUNCTION: ! DRIVER FOR COST UPDATING FOR TYPICAL UNARY OPERATOR NODES. ! ROUTINE KUNOP(NODE,UOPST,KOP)= BEGIN MAP GTVEC NODE:UOPST; LOCAL KMOV; KMOV_KKMOV(.UOPST,.NODE); UPDATE(.UOPST,(.KMOV NEQ 0)*K(UOPST),(.KMOV NEQ 0)*KX(UOPST)); UPDATE(.NODE,(.KMOV+.KOP)*K(NODE),(.KMOV+.KOP)*KX(NODE)) END; COMMENT ! KBINOP ! ! FUNCTION: ! DRIVER FOR COST UPDATING FOR TYPICAL BINARY OPERATOR NODES. ! ROUTINE KBINOP(NODE,LOPST,ROPST,KOP)= BEGIN MAP GTVEC NODE:LOPST:ROPST; LOCAL KMOV; IF .NODE[TPATH] THEN (KMOV_.LOPST;LOPST_.ROPST;ROPST_.KMOV); KMOV_KKMOV(.LOPST,.NODE); UPDATE(.ROPST,.KOP*K(ROPST),.KOP*KX(ROPST)); UPDATE(.LOPST,(.KMOV NEQ 0)*K(LOPST),(.KMOV NEQ 0)*KX(LOPST)); UPDATE(.NODE,(.KMOV+.KOP)*K(NODE),(.KMOV+.KOP)*KX(NODE)) END; COMMENT ! KASOP ! ! FUNCTION: ! DRIVER FOR COST UPDATING FOR +,- NODES. ! ROUTINE KASOP(NODE,LOPST,ROPST)= BEGIN MAP GTVEC NODE:LOPST:ROPST; BIND LEXEME LOP=LOPST; LOCAL Z; IF .NODE[NIMMF] THEN IF .NODE[MODE] GTR GENREG+DEFERRED THEN NODE[MODE]_GENREG; IF .NODE[TPATH] THEN (Z_.LOPST;LOPST_.ROPST;ROPST_.Z); Z_SUMBITS(.NODE[RCBITS]); IF .NODE[RCMTF] THEN Z_.Z-1+KKMOV(.LOPST,.NODE); UPDATE(.NODE,.Z*K(NODE),.Z*KX(NODE)); Z_IF .NODE[RCMTF] THEN IF .LOP[LTYPF] EQL GTTYP THEN (.NODE[REGF] NEQ .LOPST[REGF]); UPDATE(.LOPST,.Z*K(LOPST),.Z*KX(LOPST)); Z_.NODE[RCOPTF]*(1+KOSTOFTEMP(.ROPST)); UPDATE(.ROPST,.Z*K(ROPST),.Z*KX(ROPST)) END; COMMENT ! KSHFTOP ! ! FUNCTION: ! DRIVER FOR COST UPDATING FOR A ^ NODE. ! ROUTINE KSHFTOP(NODE,LOPST,NUM)= BEGIN LOCAL KMIN,KMAX,KMOV; MAP GTVEC NODE:LOPST; KMIN_KMAX_0; IF .NUM GEQ 8 THEN (KMIN_KMAX_1; NUM_.NUM-8); IF .NUM EQL 7 THEN KMIN_KMAX_.KMAX+4 ELSE (KMIN_KMAX_.KMAX+ABS(.NUM); IF .NUM LEQ -8 THEN KMAX_.KMIN+5); IF .NODE[NIMMF] THEN % TAKING ACCT. OF DISTRIB. MULTIPY. % IF .NODE[MODE] GTR GENREG+DEFERRED THEN NODE[MODE]_GENREG; KMOV_KKMOV(.LOPST,.NODE); UPDATE(.NODE,(.KMOV+.KMIN)*K(NODE),(.KMOV+.KMAX)*KX(NODE)); UPDATE(.LOPST,(.KMOV NEQ 0)*K(LOPST),(.KMOV NEQ 0)*KX(LOPST)) END; COMMENT ! KRELOP ! ! FUNCTION: ! DRIVER FOR COST UPDATING FOR RELATIONAL OPERATOR NODES. ! ROUTINE KRELOP(NODE,LOPST,ROPST)= BEGIN MAP GTVEC NODE; UPDATE(.LOPST,K(LOPST),KX(LOPST)); UPDATE(.ROPST,K(ROPST),KX(ROPST)); IF .NODE[NSRFRF] THEN UPDATE(.NODE,2*K(NODE),2*KX(NODE)) END; COMMENT ! LOADANALYSIS ! ! FUNCTION: ! COMPUTE NUMBER OF ACCESSES TO THE TEMP OF A LOAD NODE. ! MACRO LOADANALYSIS=(1+.NODE[RCNTF]+.NODE[RCCF]+2*.NODE[NIMMF])$; COMMENT ! CTRLKOST ! ! FUNCTION: ! DRIVER FOR COST UPDATING FOR ANY CONTROL NODE WHICH HAS ! A DEFAULT VALUE RETURNED, E.G. -1 FOR A LOOP, ETC. ! MACRO CTRLKOST=(UPDATE(.NODE,K(NODE),KX(NODE)))$; COMMENT ! IDKOST ! ! FUNCTION: ! DRIVER FOR COST UPDATING FOR INCR/DECR NODES. ! ROUTINE IDKOST(NODE)= BEGIN MAP GTVEC NODE; LOCAL O1,O3,O4; O1_.NODE[OPR1];O3_.NODE[OPR3];O4_.NODE[OPR4]; LOOPDEPTH_.LOOPDEPTH+1; UPDATE(.O1,2*K(O1),2*KX(O1)); UPDATE(.O3,K(O3),KX(O3)); UPDATE(.O4,K(O4),KX(O4)); LOOPDEPTH_.LOOPDEPTH-1; KUNOP(.O1,.NODE[OPR2],0) END; COMMENT ! KOST ! ! FUNCTION: ! MAIN COST CONTROL ROUTINE. CALLED BY TLA FOR COST UPDATING OF ! THE CURRENT NODE. SWITCHES TO THE NODE-SPECIFIC COST UPDATING ! ROUTINES. ! ROUTINE KOST(NODE)= BEGIN MAP GTVEC NODE; LOCAL GTVEC LOPST:ROPST; BIND KLABEL=2, ! EST. AVG. NUMBER OF LEAVES TO ANY LABEL MUSTBEREG=20; MACRO KAS=KASOP(.NODE,.LOPST,.ROPST)$, KUN(C)=KUNOP(.NODE,.LOPST,(C))$, KSHFT=KSHFTOP(.NODE,.LOPST,EXTEND(CLITVALUE(ROPST)))$, KREL=KRELOP(.NODE,.LOPST,.ROPST)$, KBIN(C)=KBINOP(.NODE,.LOPST,.ROPST,(C))$; IF NOT .NODE[MUSTGENCODE] THEN RETURN; IF .NODE[NODEX] GTR MAXOPERATOR THEN BEGIN SELECT .NODE[NODEX] OF NSET SYNWDO: CTRLKOST; SYNUDO: CTRLKOST; SYNDOW: CTRLKOST; SYNDOU: CTRLKOST; SSTOROP: BEGIN LOPST_IF .NODE[TPATH] THEN .NODE[OPR2] ELSE .NODE[OPR1]; ROPST_IF .NODE[TPATH] THEN .NODE[OPR1] ELSE .NODE[OPR2]; IF RESREQ THEN (KUNOP(.NODE,.ROPST,0);KUNOP(.LOPST,.NODE,0)) ELSE KUNOP(.LOPST,.ROPST,0) END; SYNIF: BEGIN LOCAL O2; O2_.NODE[OPR2]; IF RESREQ THEN (KUNOP(.NODE,.NODE[OPR3],0); KUNOP(.NODE,.NODE[OPR4],0)); UPDATE(.O2,K(O2),KX(O2)) END; SYNCASE: BEGIN LOCAL O2; O2_.NODE[OPR2]; UPDATE(.O2,MUSTBEREG*K(O2),MUSTBEREG*KX(O2)); IF RESREQ THEN INCR I FROM 2 TO .NODE[NODESIZEF]-2 DO KUNOP(.NODE,.NODE[OPERAND(.I)],0) END; SYNSEL: BEGIN MACRO OPND(I)=NODE[OPERAND(I)]$, LAST(I)=NODE[OPERAND(.NODE[NODESIZEF]-I)]$; LOCAL FO,LAS2; LOPST_.OPND(0); IF RESREQ THEN IF NOT .NODE[ROTHER] THEN CTRLKOST; IF (FO_LITVALUE(.LAST(1))) NEQ 0 THEN (LAS2_.LAST(2); UPDATE(.LAS2,K(LAS2),KX(LAS2))); INCR I FROM 1 TO .NODE[NODESIZEF]-4 BY 2 DO BEGIN IF .I LEQ .FO THEN UPDATE(.LAS2,K(LAS2),KX(LAS2)); IF (ROPST_.OPND(.I)) NEQ LEXALWAYS THEN IF .ROPST NEQ LEXOTHERWISE THEN (UPDATE(.LOPST,K(LOPST),KX(LOPST)); UPDATE(.ROPST,K(ROPST),KX(ROPST))); IF RESREQ THEN KUNOP(.NODE,.OPND(.I+1),0) END END; SYNINCR: IDKOST(.NODE); SYNDECR: IDKOST(.NODE); SFPARM: BEGIN LOPST_.NODE[OPR1]; KUN(LOADANALYSIS); END; SYNLABEL: IF RESREQ THEN KUNOP(.NODE,.NODE[OPR1],IF .GT[.NODE[OPR2],LEFTBIT] THEN KLABEL ELSE 1) TESN END ELSE BEGIN IF NOT RESREQ THEN RETURN; LOPST_.NODE[OPR1]; IF .NODE[NODESIZEF] GEQ 2 THEN ROPST_.NODE[OPR2]; IF ISRELOP(NODE) THEN KREL ELSE SELECT .NODE[NODEX] OF NSET SADDOP: KAS; SSWABOP: KUN(1); SMINOP: KAS; SPLUSOP: KUN(LOADANALYSIS); SANDOP: KBIN(2); SOROP: KBIN(2); SXOROP: KBIN(4); SEQVOP: KBIN(4); SMAXOP: KBIN(2); SMINNOP: KBIN(2); SSHIFTOP: KSHFT; SROTOP: (LOCAL X; X_EXTEND(CLITVALUE(ROPST));X_ABS(.X); KUN(IF .X GTR 8 THEN 17-.X ELSE .X)); OTHERWISE: 0 TESN END END; ! THE FOLLOWING ROUTINES,ETC., ARE CONCERNED ! WITH DETERMINING THE LIFE 'SPAN' OF A TEMP NAME. ! THE 'SPAN' IS DEFINED IN TERMS OF TWO QUANTITIES, ! THE 'LON' AND 'FON'. (SEE THE TNBIND DOCUMENTATION ! FOR THE DEFINITION AND USE OF THESE). ! ! THE PROCESS OF DETERMINING THE 'SPAN' IS ACCOMPLISHED ! BY A SINGLE ROUTINE 'SPAN' AND A NUMBER OF NODE-SPECIFIC ! DRIVERS FOR SPAN. FOR EXAMPLE, ALL BINARY OPERATORS ! INVOKE THE ROUTINE 'SPANBINARY' WHICH, IN TURN,, ! MAKES SEVERAL CALLS ON SPAN. ! ! MACRO NEXTLON=(LON_.LON+1)$, NEXTFON=(FON_.FON+1)$, SAVDTD=(PUSHLS(DTDSTK,.DTEMPS[CURD]); DTDSTK[MDTD]_#777777)$, POPDTD=(POPLS(DTDSTK))$; COMMENT ! RESETDTD ! ! FUNCTION: ! USED AFTER EACH BRANCH OF A FORK. KEEPS TRACK (IN MDTD) OF THE ! LOWEST LEVEL TO WHICH ANY BRANCH RAISED DTEMPS[CURD] (THE ! DYNAMIC TEMPS STACK DEPTH). ALSO RESETS THE DYTEMP STACK TO ! WHATEVER IT WAS BEFORE THE BRANCH. ! MACRO RESETDTD=(IF .DTEMPS[CURD]LSS.DTDSTK[MDTD]THEN DTDSTK[MDTD]_ .DTEMPS[CURD]; CLOSEDYTEMPS(.DTDSTK[LDTD]))$; COMMENT ! MINDTD ! ! FUNCTION: ! USED AFTER AN ENTIRE FORK. CUTS BACK THE DYTEMPS STACK ! TO THE MINIMUM HEIGHT, KEPT TRACK OF AS NOTED ABOVE. ! MACRO MINDTD=(IF .DTEMPS[CURD] LSS .DTDSTK[MDTD] THEN DTDSTK[MDTD]_.DTEMPS[CURD]; CLOSEDYTEMPS(.DTDSTK[MDTD]))$; MACRO NOTEDTD=NODE[DTDELETE]_-1 %(.DTEMPS[CURD]+1)*2% $, SAVFON= PUSHLS(FONSTK,(.FON^18+.FON))$, RESETFON=(IF .FON GTR .FONSTK[MFON] THEN FONSTK[MFON]_.FON; FON_.FONSTK[LFON])$, MAXFON=(IF .FONSTK[MFON] GTR .FON THEN FON_.FONSTK[MFON]; POPLS(FONSTK))$; MACRO UPDATELONFON=(NODE[LONF]_NEXTLON; NODE[FONF]_NEXTFON)$, LABELWORD(Z1,Z2)=((Z1)^18 OR ((Z2) AND #777777))$, ASSIGNLABELS= IF .LABS NEQ 0 THEN IF LABSNEEDED THEN BEGIN LOCAL GTVEC T; NODE[LABELW]_.LABS; IF (T_.LABS[LTF]) NEQ 0 THEN T[LABELREQDF]_1; IF (T_.LABS[LFF]) NEQ 0 THEN T[LABELREQDF]_1; END$; MACRO TNF=0,18$, LTF=18,18$, LFF=0,18$; MACRO NOTELOOP(Z,LD)=(LINK(TNREP(Z),LOOPSTK[LSELEM(LD)]))$; MACRO ISGTLEX(X)=(BIND LEXEME L=(X); .L[LTYPF] EQL GTTYP)$, LABSNEEDED=(.NODE[NSRFFF])$, FLOWRES=(.NODE[NSRFF] EQL RFFLOW)$, TNNEEDED=(.NODE[NSRFRF])$; MACRO SETNOTFPARM= (LOCAL A; A_.DTEMPS[CURD]+1; IF .A GTR .DTEMPS[MAXD] THEN EXITBLOCK; REOPEN(DTEMPS[LSELEM(.A)],.LON,.FON); CLOSELIST(DTEMPS[LSELEM(.A)],.LON) )$; COMMENT ! KILLPDTEMPS ! ! FUNCTION: ! MAKES SURE THAT CODE WILL BE GENERATED TO CLEAN UP THE STACK ! DOWN TO LEVEL 'NUM', AFTER CODING OF 'NODE'. ! ROUTINE KILLPDTEMPS(NODE,NUM)= BEGIN MAP GTVEC NODE; BIND LEXEME LEX=NODE; IF .LEX[LTYPF] NEQ GTTYP THEN RETURN; CLOSEDYTEMPS(.NUM); NODE[DTDELETE]_(.NUM+1)*2; END; COMMENT ! KLCLEANUP ! ! FUNCTION: EXIT ROUTINE FOR KILLDYTEMPS AND KILLFORKDYTEMPS ! MAKES SURE APPROPRIATE SUBNODES PUT OUT STACK CLEANUP ! CODE IF NECESSARY (I.E. IF THEY ARE LIKELY TO CAUSE ! BRANCHES TO LABELS PAST THE NODE'S STACK CLEANUP CODE) ! ROUTINE KCLEANUP(ROUT,NODE)= BEGIN MAP GTVEC NODE; IF .NODE[NODEX] EQL SYNCOMP THEN RETURN (.ROUT)(.NODE[LASTOPERAND]); IF NOT FLOWRES THEN IF NOT (IF ISRELOP(NODE) THEN .GT[.NODE[OPR1],NODEX] EQL SBITOP OR .GT[.NODE[OPR2],NODEX] EQL SBITOP) THEN RETURN; IF .NODE[NODEX] EQL SYNIF THEN ((.ROUT)(.NODE[OPR3]); (.ROUT)(.NODE[OPR4]); RETURN); IF .NODE[NODEX] EQL SYNCASE THEN (INCR I FROM 2 TO .NODE[NODESIZEF]-2 DO (.ROUT)(.NODE[OPERAND(.I)]); RETURN); % AT THIS POINT, NODE MUST BE AND, OR, OR NOT % (.ROUT)(.NODE[OPR1]); IF .NODE[NODESIZEF] EQL 2 THEN (.ROUT)(.NODE[OPR2]); END; COMMENT ! KILLFORKDYTEMPS ! ! FUNCTION: ! USED ON EACH BRANCH OF A FORK AFTER MINDTD. MAKES SURE THAT ! CODE TO CLEAN UP THE STACK IS GENERATED AFTER EACH BRANCH. ! ROUTINE KILLFORKDYTEMPS(NODE)= BEGIN MAP GTVEC NODE; BIND LEXEME LEX=NODE; IF .LEX[LTYPF] NEQ GTTYP THEN RETURN NOVALUE; NODE[DTDELETE]_(.DTDSTK[MDTD]+1)*2; KCLEANUP(KILLFORKDYTEMPS,.NODE); RETURN NOVALUE END; ROUTINE KILLDYTEMPS(NODE)= BEGIN MAP GTVEC NODE; BIND LEXEME LEX=NODE; IF .LEX[LTYPF] NEQ GTTYP THEN RETURN NOVALUE; CLOSEDYTEMPS(.DTDSTK[LDTD]); NODE[DTDELETE]_(.DTDSTK[LDTD]+1)*2; KCLEANUP(KILLDYTEMPS,.NODE); RETURN NOVALUE END; MACRO TNSPAN(XTN)=(IF .XTN GTR 8 THEN (XTN[LONLU]_.LON;XTN[FONLU]_.FON))$, INITTNSPAN(XTN)=(IF .XTN GTR 8 THEN (XTN[FONFU]_XTN[FONLU]_.FON;XTN[LONFU]_XTN[LONLU]_.LON))$; ROUTINE SPAN(NODE,INC)= BEGIN MAP GTVEC NODE; BIND LEXEME NLEX=NODE; LOCAL GTVEC TN,FFU,FLU,LD; IF .NLEX[LTYPF] EQL BNDVAR THEN (IF NOT ONEOF(.NODE[TYPEF],BIT3(REGT,LOCALT,FORMALT)) THEN RETURN NOVALUE) ELSE IF .NLEX[LTYPF] NEQ GTTYP THEN RETURN NOVALUE ELSE IF .NODE[NODEX] EQL SYNCOMP THEN SPAN(.NODE[LASTOPERAND],.INC); IF (TN_.NODE[REGF]) GTR 8 THEN BEGIN IF .TN[TNLITBIT] THEN RETURN NOVALUE; IF .TN[LONLU] LSS .LON THEN TN[LONLU]_.LON-.INC; IF (FLU_.TN[FONLU]) LSS .FON THEN FLU_TN[FONLU]_.FON-.INC; IF .TN[LONFU] GTR .LON THEN TN[LONFU]_.LON; IF (FFU_.TN[FONFU]) GTR .FON THEN FFU_TN[FONFU]_.FON; IF .NLEX[LTYPF] EQL GTTYP THEN LD_MIN(.TN[LDF],.NODE[GTLDF]) ELSE LD_.TN[LDF]; IF .LD LSS .LOOPDEPTH THEN NOTELOOP(.TN,.LD); IF ONEOF(.TN[REQD],BIT3(NOREQDB,DECREQDB,RFREQDB)) THEN IF .MAXFONSPAN LSS .FLU-.FFU THEN MAXFONSPAN_.FLU-.FFU; SELECT .TN[REQD] OF NSET MEMREQDB: EXITSELECT NODE_.TN[REGF]; RFREQDB: EXITSELECT NODE_.TN[OFFSETF]; ALWAYS: RETURN NOVALUE TESN; SELECT .NODE[TYPEF] OF NSET TEMPNAMET: RETURN NOVALUE; GRAPHT: RETURN SPAN(FASTLEXOUT(GTTYP,.NODE),.INC); OTHERWISE: RETURN SPAN(FASTLEXOUT(BNDVAR,.NODE),.INC) TESN END; NOVALUE END; ROUTINE SPANBINARY(NODE)= BEGIN MAP GTVEC NODE; LOCAL LEXEME TN; MACRO SPC=(.TN[SSPF] NEQ PFE1)$; SPAN(.NODE,0); IF .NODE[TPATH] THEN (TN_.NODE[OPR2]; SPAN(.NODE[OPR1],0)) ELSE (TN_.NODE[OPR1]; SPAN(.NODE[OPR2],0)); SPAN(.TN,SPC) END; ROUTINE AOSPAN(NODE)= BEGIN MAP GTVEC NODE; IF NOT FLOWRES THEN SPANBINARY(.NODE) END; ROUTINE SPANBXNARY(NODE)= BEGIN MAP GTVEC NODE; SPAN(.NODE,0); SPAN(.NODE[OPR1],0); SPAN(.NODE[OPR2],0) END; ROUTINE SPANSTORE(NODE)= BEGIN MAP GTVEC NODE; LOCAL LEXEME L; BIND GTVEC LST=L; MACRO SC=IF NOT RESREQ THEN 0 ELSE IF .L[LTYPF] NEQ GTTYP THEN 1 ELSE IF .LST[NODEX] LEQ MAXOPERATOR THEN (.L[SSPF] NEQ PFE1)$; SPAN(.NODE,0); IF .NODE[TPATH] THEN (L_.NODE[OPR1]; SPAN(.NODE[OPR2],0)) ELSE (L_.NODE[OPR2]; SPAN(.NODE[OPR1],0)); SPAN(.L,SC) END; ROUTINE SPANUNARY(NODE)= BEGIN MAP GTVEC NODE; SPAN(.NODE,0); SPAN(.NODE[OPR1],1) END; ROUTINE SPANUXNARY(NODE)= BEGIN MAP GTVEC NODE; SPAN(.NODE,0); SPAN(.NODE[OPR1],0) END; ROUTINE SPANUX(NODE)= BEGIN MAP GTVEC NODE; SPAN(.NODE,0) END; ROUTINE SPANLOADNODE(NODE)= BEGIN REGISTER LEXEME OP; MAP GTVEC NODE; SPAN(.NODE,0); OP_.NODE[OPR1]; IF .OP[LTYPF] EQL BNDVAR THEN SPAN(.OP,0) ELSE IF .OP[SSPF] EQL PFE1 THEN SPAN(.OP,0); NOVALUE END; ROUTINE SPANID(NODE)= BEGIN MAP GTVEC NODE; SPAN(.NODE,0); SPAN(.NODE[OPR1],1); SPAN(.NODE[OPR3],1); SPAN(.NODE[OPR4],1) END; MACRO INITLOOP=(INITSTK(LOOPSTK);INITLS(LOOPLFSTK))$, RELEASELOOP=RELEASESPACE(GT,.LOOPSTK,STKSIZE)$; ROUTINE ENTLOOP=(PUSHSTK(LOOPSTK); NEXTLON; NEXTFON; PUSHLS(LOOPLFSTK,.LON^18+.FON); LOOPDEPTH_.LOOPDEPTH+1); ROUTINE XITLOOP= BEGIN LOCAL L,GTVEC T; FORALLTN(T,LOOPSTK[TOS], BEGIN IF .T[FONFU] GTR .LOOPLFSTK[LEFON] THEN T[FONFU]_.LOOPLFSTK[LEFON]; IF .T[LONFU] GTR .LOOPLFSTK[LELON] THEN T[LONFU]_.LOOPLFSTK[LELON]; IF .T[FONLU] LSS .FON THEN T[FONLU]_.FON; IF ONEOF(.T[REQD],BIT3(NOREQDB,DECREQDB,RFREQDB)) THEN (L_.T[FONLU]-.T[FONFU]; IF .L GTR .MAXFONSPAN THEN MAXFONSPAN_.L); IF .T[LONLU] LSS .LON THEN T[LONLU]_.LON END); LOOPDEPTH_.LOOPDEPTH-1; POPSTK(LOOPSTK); POPLS(LOOPLFSTK); NOVALUE END; COMMENT ! BINDUSES ! ! FUNCTION: ! 'NODE' IS A CSE. ASSIGN THE SAME TN TO ! ALL THE OCCURRENCES OF THE CSE. ! ROUTINE BINDUSES(NODE)= BEGIN MAP GTVEC NODE; REGISTER GTVEC PNODE:T; PNODE_.NODE[CSPARENT]; PNODE[BOUND]_1; ! SAVES SOME TROUBLE FOR BOGUS NODES IF (T_.NODE[REGF]) LSS 8 THEN RETURN; IF .T[REQD] EQL 0 THEN T[REQD]_DECREQDB; ! TREAT CSE'S LIKE DECLARED TN'S DO (IF .PNODE[NSRFF] NEQ RFNONE THEN PNODE[REGF]_.T; IF NOT (.PNODE[DELAYED] AND .PNODE[MUSTGENCODE]) THEN PNODE[BOUND]_1) UNTIL (PNODE_.PNODE[CSTHREAD]) EQL 0; NOVALUE END; ! B. - SPECIFIC ROUTINES ! ------------------------------------------------ ! ! ! THIS SECTION CONTAINS THE NODE-SPECIFIC TN ASSIGNMENT ! ROUTINES. THE FLOW WITHIN THESE ROUTINES IS A BIT ! INVOLUTED - A BIT OF EXPLANATION IS PROBABLY IN ORDER: ! ! 1) ASSIGNMENT IS DONE IN AN EXECUTION-ORDER TREE WALK. ! EACH ROUTINE TENDS TO DO A BIT OF WORK AT A NODE THEN ! CALL OTHER BINDERS TO WORK ON ITS SUBNODES, AND FINALLY ! DOES A BIT MORE AT ITS OWN NODE BEFORE RETURNING. ! ! 2) SINCE EACH TYPE OF NODE HAS A ROUTINE TO HANDLE ! IT, THE ROUTINE 'TLA' ACTS AS A SWITCH TO CALL THE ! APPROPRIATE ONE. THAT IS, EACH NODE CALLS 'TLA' ON ITS ! SUBNODES, AND TLA PROMPTLY SWITCHES OFF TO THE ! SPECIFIC ROUTINE. ! ! 3) SINCE MANY OF THE ACTIONS OF BINDING ARE COMMON TO ! EACH OF THE SPECIFIC ROUTINES, A SINGLE ROUTINE, ! 'TLCOMMON', HANDLES THESE IN MOST CASES. IN THESE ! CASES, TLCOMMON CALLS ANOTHER ROUTINE TO PERFORM THE ! NODE-SPECIFIC ACTIONS. TLCOMMON ALSO CALLS THE SPAN ROUTINE ! WHICH IS APPROPRIATE FOR THE SPECIFIC NODE. ! ! THE MACRO 'TLRDEF' IS USED TO DEFINE A TN ASSIGNMENT ! ROUTINE CALLED BY 'TLA'. THE MACRO 'NDRDEF' IS USED ! TO DEFINE A NODE-SPECIFIC ROUTINE CALLED BY TLCOMMON. ! ! ! %< ROUTINE TNWALK(NODE)= BEGIN MAP GTVEC NODE; LOCAL GTVEC N; BIND LEXEME L=N; INCR I FROM 0 TO .NODE[NODESIZEF]-1 DO BEGIN N_.NODE[OPERAND(.I)]; IF .L[LTYPF] EQL GTTYP THEN IF .N[MUSTGENCODE] THEN TLA(.N,0,0) ELSE TNWALK(.N) END; NOVALUE END; >% FORWARD TLCOMMON; MACRO SETBOUND=NODE[BOUND]_1$; ROUTINE TLLIST(NODE,P)= BEGIN MAP GTVEC NODE; LOCAL L; L_.NODE[MUSTGENCODE]; NODE[MUSTGENCODE]_1; TLA(.NODE,0,0); BINDUSES(.NODE); NODE[MUSTGENCODE]_.L; NOVALUE END; ROUTINE LOOPTLLIST(NODE,P)= (MAP GTVEC NODE; TLLIST(.NODE,.P); IF (NODE_.NODE[REGF]) GEQ 8 THEN IF .NODE[LDF] GTR .LOOPDEPTH THEN NODE[LDF]_.LOOPDEPTH; NOVALUE); ROUTINE BINDLST(N)=(PULSELIST(TLLIST<0,0>,.N,0); FIXLIST(.N)); ROUTINE LPBINDLST(N)=(PULSELIST(LOOPTLLIST<0,0>,.N,0); FIXLIST(.N)); MACRO TLRDEF(NAME,BODY)= ROUTINE ID(TL)NAME(NODE,TX,LABS)= ( MAP GTVEC NODE, TNWORD TX:LABS; BODY)$; MACRO NDRDEF(NAME,BODY)= ROUTINE ID(ND)NAME(NODE,TX,LABS)= ( MAP GTVEC NODE, TNWORD TX:LABS; BODY)$; TLRDEF(NULL,(NOTEDTD; 0)); NDRDEF(B,( BEGIN LOCAL LOP,ROP,OP1; BIND TEMP=LABS; LOP_ROP_0; IF .NODE[TPATH] THEN (ROP_.TX;OP1_.NODE[OPR2]) ELSE (LOP_.TX;OP1_.NODE[OPR1]); LOP_TLA(.NODE[OPR1],.LOP,0); ROP_TLA(.NODE[OPR2],.ROP,0); IF .NODE[TPATH] THEN LOP_.ROP; IF NOT RESREQ THEN RETURN .LOP; TEMP_0; IF .TX EQL 0 THEN IF ISDESTROYABLE(OP1) THEN TX_.LOP ELSE TEMP_.LOP; IF TNNEEDED THEN (FILLTX; WANTPREF(.TX,.TEMP)); .TX END)); NDRDEF(U,TLA(.NODE[OPR1],.TX,.LABS)); ROUTINE ISBIT(LEX)= BEGIN MAP LEXEME LEX; BIND GTVEC NODE=LEX; IF .LEX[LTYPF] EQL GTTYP THEN IF .NODE[NODEX] EQL SBITOP THEN (TNNEEDED)^1 + 1 END; NDRDEF(REL,( BEGIN LOCAL LOP,ROP,LB1,LB2; BIND BITLEFT =ISBIT(.NODE[OPR1]), BITRIGHT=ISBIT(.NODE[OPR2]); IF TNNEEDED OR (BITLEFT OR BITRIGHT)^(-1) THEN FILLTX ELSE TX_0; LOP_ROP_LB1_LB2_0; IF BITLEFT THEN (LOP_.TX; LB1_.LABS) ELSE IF BITRIGHT THEN (ROP_.TX; LB2_.LABS); LOP_TLA(.NODE[OPR1],.LOP,.LB1); ROP_TLA(.NODE[OPR2],.ROP,.LB2); IF BITLEFT THEN WANTPREF(.TX,.LOP) ELSE IF BITRIGHT THEN WANTPREF(.TX,.ROP); .TX END)); NDRDEF(FSTO,( BEGIN LOCAL UOP; UOP_TLA(.NODE[OPR1],0,0); IF RESREQ THEN (FILLTX; WANTPREF(.TX,.UOP)); .TX END)); NDRDEF(SWAB,( BEGIN LOCAL UOP; UOP_TLA(.NODE[OPR1],.TX,0); IF RESREQ THEN IF ISDESTROYABLE(NODE[OPR1]) THEN TX_.UOP ELSE (FILLTX; WANTPREF(.TX,.UOP)); .TX END)); NDRDEF(FPAR,( BEGIN LOCAL GTVEC UOP:PARM; BIND LEXEME PARMLEX=PARM; UOP_TLA(PARM_.NODE[OPR1],0,0); IF .NODE[CSCOMPL] LEQ MAGIC2 THEN IF .UOP GTR 8 THEN IF .UOP[REQD] EQL 0 THEN IF .PARMLEX[LTYPF] EQL GTTYP THEN IF ISDESTROYABLE(PARM) THEN IF .PARM[MODE] EQL GENREG THEN EXITBLOCK .UOP; TX_GETTN(); WANTPREF(.TX,.UOP); .TX END)); MACRO ISNCSE(TN) = (IF TN GEQ 8 THEN .GT[TN,BNDTYP] EQL BNDNCSE) $, FIXLDF(TN) = (GT[TN,LDF]_.LOOPDEPTH) $; NDRDEF(LOADNODE,( BEGIN LOCAL UOP,LEXEME OP1; OP1_.NODE[OPR1]; UOP_TLA(.OP1,0,0); IF ISNCSE(.NODE[REGF]) THEN FIXLDF(.NODE[REGF]); IF RESREQ THEN (FILLTX; IF .OP1[LTYPF] NEQ BNDVAR THEN WANTPREF(.TX,.UOP)); .TX END)); NDRDEF(ADDSUB,( BEGIN LOCAL LOP,ROP,OP1,TN; BIND TEMP=LABS; LOP_ROP_0; IF .NODE[TPATH] THEN (ROP_.TX;OP1_.NODE[OPR2]) ELSE (LOP_.TX;OP1_.NODE[OPR1]); LOP_TLA(.NODE[OPR1],.LOP,0); ROP_TLA(.NODE[OPR2],.ROP,0); IF .NODE[TPATH] THEN LOP_.ROP; IF NOT RESREQ THEN RETURN .LOP; TN_TEMP_0; IF ISDESTROYABLE(OP1) THEN TN_.LOP ELSE TEMP_.LOP; IF .TN GEQ 8 THEN TX_.TN ELSE IF TNNEEDED THEN BEGIN IF NOT (.NODE[RCMTF] AND NOT .NODE[OLDRCMTF]) THEN IF NOT .NODE[RCMOF] THEN TX_.TEMP; FILLTX; WANTPREF(.TX,.TEMP); END; .TX END)); TLRDEF(DOT,( BEGIN BIND LEXEME LEX=NODE; IF ISCSEUSE(NODE) THEN BEGIN LOCAL GTVEC PAR; PAR_.NODE[CSPARENT]; IF NOT .PAR[BOUND] THEN (IF NOT .PAR[DELAYED] ! PAR IS A BOGUS NODE THEN NONBOGUS(PAR); IF .PAR NEQ .LEX[ADDRF] THEN TLLIST(FASTLEXOUT(GTTYP,.PAR),0)) END ELSE BEGIN TX_TLA(.NODE[OPR1],.TX,.LABS); IF .NODE[REGF] EQL 0 THEN NODE[REGF]_.TX; IF ISCSECREATION(NODE) THEN BINDUSES(.NODE); END; NOTEDTD; UPDATELONFON; SETBOUND; ASSIGNLABELS; SPANUXNARY(.NODE); .NODE[REGF] END)); ROUTINE BINDSTORE(LOP,ROP)= BEGIN MAP GTVEC LOP:ROP; BIND LEXEME LLOP=LOP; LOCAL SVLON,SVFON; IF .ROP LEQ 7 THEN RETURN NOVALUE; IF .ROP[REQD] NEQ 0 THEN RETURN NOVALUE; ROP[REQD]_MEMREQDB; IF .LLOP[LTYPF] EQL LITTYP THEN BEGIN ROP[TNLITBIT]_1; ROP[TNLITLEX]_.LOP; ROP[BNDTYP]_0; RETURN NOVALUE END; ROP[REGF]_.LOP; UPDATE(.LOP,.ROP[USECOMPLEXITY]/(.LOOPDEPTH+1),.ROP[XUSECOMPLEXITY]/(.LOOPDEPTH+1)); SVLON_.LON; SVFON_.FON; LON_.ROP[LONFU]; FON_.ROP[FONFU]; SPAN(.LOP,0); LON_.SVLON; FON_.SVFON; NOVALUE END; ROUTINE FINDLEX(LEX,TREE)= BEGIN MAP LEXEME LEX, GTVEC TREE; BIND LEXEME TLEX=TREE; MACRO FINDNCSE(NODE)= (MAP GTVEC NODE; IF .NODE[REGF] LEQ 7 THEN RETURN 0 ELSE IF .GT[.NODE[REGF],BNDTYP] NEQ BNDNCSE THEN RETURN 0 ELSE NODE_.GT[.NODE[REGF],OFFSETF]; IF .NODE[TYPEF] EQL GRAPHT THEN RETURN 0; NODE_BNDVAR)$; IF .LEX[LTYPF] EQL GTTYP THEN FINDNCSE(LEX); IF .TLEX[LEXPART] EQL .LEX[LEXPART] THEN RETURN 1; IF .TLEX[LTYPF] EQL GTTYP THEN IF .TREE[NODEX] EQL SYNNULL THEN (FINDNCSE(TREE); RETURN FINDLEX(.LEX,.TREE)) ELSE INCR I FROM 0 TO .TREE[NODESIZEF]-1 DO IF FINDLEX(.LEX,.TREE[OPERAND(.I)]) THEN RETURN 1; 0 END; ROUTINE FINDLEFT(LN,RN)= BEGIN LOCAL X,Y; MAP GTVEC LN:RN; BIND LEXEME LRN=RN; IF .LRN[LTYPF] NEQ GTTYP THEN RETURN 0; IF .RN[NODEX] EQL SDOTOP THEN RETURN (.RN[OPR1] EQL .LN); IF NOT (ONEOF(.RN[NODEX],BIT5(SADDOP,SMINOP,SANDOP,SOROP,SSWABOP)) OR ONEOF(.RN[NODEX]-2,BIT6(SSHIFTOP-2,SROTOP-2, SMAXOP-2,SMINNOP-2,SEQVOP-2,SXOROP-2))) THEN RETURN 0; IF .RN[TPATH] THEN (X_.RN[OPR2];Y_.RN[OPR1]) ELSE (Y_.RN[OPR2];X_.RN[OPR1]); IF .RN[NODESIZEF] EQL 2 THEN IF FINDLEX(.LN,.Y) THEN RETURN 0; IF (Y_FINDLEFT(.LN,.X)) NEQ 0 THEN .Y+1 ELSE 0 END; ROUTINE ISNEGNOT(LN,RN)= BEGIN MAP GTVEC LN:RN; LOCAL GTVEC LRN:LLRN; BIND LEXEME LNLEX=LN:RNLEX=RN:LRNLEX=LRN:LLRNLEX=LLRN; IF .RNLEX[LTYPF] NEQ GTTYP THEN RETURN 0; IF .RN[NODEX] NEQ SNEGOP THEN IF .RN[NODEX] NEQ SNOTOP THEN RETURN 0; LRN_.RN[OPR1]; IF .LRNLEX[LTYPF] NEQ GTTYP THEN RETURN 0; IF .LRN[NODEX] NEQ SDOTOP THEN RETURN 0; LLRN_.LRN[OPR1]; IF EQLPOSSIZE(.LN,.LLRN) THEN RETURN 1; 0 END; ROUTINE SIMPLESTORE(LN,RN)= BEGIN ! ! A "SIMPLE" STORE IS, BY DEFINITION, ONE WHICH DOES NOT ! NEED A SPECIAL TEMPORARY FOR THE RHS. ! ! VALUE RETURNED: ! -1 :: WE HAVE A STORE OF THE FORM ! (EXPR1) _ .(EXPR1) OP (EXPR2), ! OR (EXPR1) _ NOT .(EXPR1) ! OR (EXPR1) _ - .(EXPR2); ! THE 'RCMTF' BIT OF THE 'OP' (OR 'NOT' OR '-') NODE ! SHOULD BE TURNED OFF. ! 1 :: WE HAVE SOME OTHER KIND OF SIMPLE STORE, E.G. ! VAR1 _ .VAR2 + 3; ! THE 'RCMTF' BIT OF THE 'OP' NODE SHOULD BE LEFT AS IS. ! 0 :: THE STORE WE ARE DEALING WITH IS NOT SIMPLE. ! MACRO ADDORSUB=ONEOF(.RN[NODEX],BIT2(SADDOP,SMINOP))$, ANDORIOR=ONEOF(.RN[NODEX],BIT2(SANDOP,SOROP))$, SPECIALCASES= NOT ONEOF(.RN[NODEX],(BIT3(SPLUSOP,SXOROP,SEQVOP) OR BMSKX(SGTROP,6) OR BMSKX(SGTRUOP,6)))$; MAP GTVEC LN:RN; LOCAL GTVEC LRN:LLRN, RRN; BIND LEXEME LNLEX=LN:RNLEX=RN:LRNLEX=LRN:LLRNLEX=LLRN; BIND SIMPLEVAL=3; ROUTINE SIMPLOP(NODE)= (MAP GTVEC NODE; IF .NODE[NODEX] LEQ MAXOPERATOR THEN 1 ELSE IF .NODE[NODEX] EQL SYNNULL THEN 1 ELSE IF .NODE[NODEX] EQL SSTOROP THEN SIMPLOP(IF .NODE[TPATH] THEN .NODE[OPR1] ELSE .NODE[OPR2])); ROUTINE ISPSOK(LN,RN)= BEGIN MAP GTVEC LN:RN; BIND LEXEME LNLEX=LN:RNLEX=RN; LOCAL SSP; MACRO ISBISORBIC= (IF ANDORIOR THEN (LOCAL LEXEME RRN:LRN; IF .RN[TPATH] THEN (LRN_.RN[OPR2]; RRN_.RN[OPR1]) ELSE (LRN_.RN[OPR1]; RRN_.RN[OPR2]); (1 AND (.RRN[KNOTF] EQV (.RN[NODEX] EQL SANDOP))) + .LRN[KNOTF]*2 ))$; MACRO ISINCORDEC= (IF ADDORSUB THEN IF ABS(EXTEND(.RN[OFFSETF])) EQL 1 THEN (.RN[RCAF] OR .RN[RCSF]))$; MACRO ISCOMORNEG= (IF .RN[NODEX] EQL SPLUSOP THEN (.RN[RCCF] OR .RN[RCNTF]))$; SSP_.LNLEX[SSPF]; IF .SSP LEQ PF016 THEN TRUE ELSE IF .SSP LEQ PF08 THEN (IF ISINCORDEC THEN TRUE ELSE IF ISCOMORNEG THEN TRUE ELSE ISBISORBIC) ELSE (ISBISORBIC EQL 1) END; IF .RNLEX[LTYPF] NEQ GTTYP THEN RETURN 0; IF .LNLEX[LTYPF] EQL GTTYP THEN BEGIN MACRO PROCEED=EXITBLOCK$; IF .LN[NODEX] EQL SYNPOI THEN IF ISPSOK(.LN,.RN) THEN PROCEED; IF NOT SIMPLOP(.LN) THEN RETURN 0 END; IF .LNLEX[LTYPF] EQL BNDVAR THEN BEGIN LOCAL X; IF .LNLEX[LEXPART] EQL .PCREG THEN RETURN 0; ! LATER THIS WILL BE EXTENDED TO ALL ! VOLATILE LOCATIONS. IF NOT ISPSOK(.LN,.RN) THEN RETURN 0; IF (X_FINDLEFT(.LN,.RN)) NEQ 0 THEN IF .X LEQ (SIMPLEVAL+1)/(1+(.LN[MODE] NEQ GENREG)) THEN RETURN -1 END; IF .RN[NODEX] EQL SPLUSOP THEN RETURN IF .RN[OCCF] EQL 1 THEN IF .RN[CSCOMPL] EQL 0 THEN 1 ELSE IF ISNEGNOT(.LN,.RN[OPR1]) THEN -1; IF .RN[NODEX] EQL SFSTORE THEN RETURN 1; IF .RN[NODEX] LEQ MAXOPERATOR THEN IF .RN[NODEX] EQL SDOTOP THEN RETURN 0 ELSE IF .RN[NODEX] EQL SSWABOP THEN RETURN 1 ELSE IF .RN[NODESIZEF] EQL 2 THEN BEGIN MACRO PROCEED=EXITBLOCK$; IF .RN[TPATH] THEN (LRN_.RN[OPR2]; RRN_.RN[OPR1]) ELSE (LRN_.RN[OPR1]; RRN_.RN[OPR2]); IF .RN[REGF] EQL .LRN[REGF] THEN IF .RN[CSCOMPL] GTR SIMPLEVAL THEN PROCEED; IF FINDLEX(.LN,.LRN) THEN IF SPECIALCASES THEN PROCEED ELSE RETURN 0; IF .LNLEX[SSPF] GTR PF016 THEN PROCEED; IF .LRNLEX[LTYPF] EQL GTTYP THEN IF .LRN[NODEX] EQL SFSTORE THEN RETURN 0; RETURN 1 - FINDLEX(.LN,.RRN) END; IF BEGIN MACRO TRUNC(X)=(X-MAXOPERATOR)$;; ONEOF(TRUNC(.RN[NODEX]),BIT4(TRUNC(SYNIF),TRUNC(SYNCASE), TRUNC(SYNSEL),TRUNC(SYNLABEL))) END THEN RETURN 1 ELSE IF .RN[NODEX] LEQ MAXOPERATOR THEN BEGIN LRN_IF .RN[TPATH] THEN .RN[OPR2] ELSE .RN[OPR1]; IF .LRNLEX[LTYPF] NEQ GTTYP THEN RETURN 0; IF .LRN[NODEX] EQL SDOTOP THEN BEGIN LLRN_.LRN[OPR1]; IF .LLRN EQL .LN THEN RETURN -(SPECIALCASES) ELSE IF EQLPOSSIZE(.LLRN,.LN) THEN IF SPECIALCASES THEN (LRN[CODED]_1; LRN[MODE]_0; LRN[REGF]_.RN[REGF]; RETURN -1); END; END; 0 END; ROUTINE TRYSIMPLESTORE(NODE,LN,RN)= BEGIN MAP GTVEC NODE:LN:RN; BIND LEXEME LNLEX=LN:RNLEX=RN; WHILE 1 DO BEGIN MACRO DOBIND=(LOCAL SMPL; SMPL_SIMPLESTORE(.LN,.RN); IF .SMPL THEN (BINDSTORE(.LN,.RN[REGF]); IF .SMPL LSS 0 THEN RN[RCMTF]_FALSE; TRUE) )$; IF .RNLEX[LTYPF] NEQ GTTYP THEN RETURN NOVALUE; IF .RN[NODEX] LEQ MAXOPERATOR THEN RETURN DOBIND; SELECT .RN[NODEX] OF NSET SYNIF: BEGIN IF DOBIND THEN (TRYSIMPLESTORE(.NODE,.LN,.RN[OPR3]); TRYSIMPLESTORE(.NODE,.LN,.RN[OPR4]) ); RETURN NOVALUE END; SYNCASE: BEGIN IF DOBIND THEN INCR I FROM 2 TO .RN[NODESIZEF]-2 DO TRYSIMPLESTORE(.NODE,.LN,.RN[OPERAND(.I)]); RETURN NOVALUE END; SYNSEL: BEGIN IF DOBIND THEN INCR I FROM 2 TO .RN[NODESIZEF]-3 BY 2 DO TRYSIMPLESTORE(.NODE,.LN,.RN[OPERAND(.I)]); RETURN NOVALUE END; SYNCOMP: CONTINUE RN_.RN[OPERAND(.RN[NODESIZEF]-1)]; SYNLABEL: (DOBIND; RETURN NOVALUE); SFSTORE: DOBIND; ALWAYS: RETURN NOVALUE TESN; END; NOVALUE END; NDRDEF(STORE,( BEGIN BIND TEMP=LABS; LOCAL LEXEME LOP:ROP; IF .NODE[TPATH] THEN (LOP_.NODE[OPR2]; ROP_.NODE[OPR1]) ELSE (LOP_.NODE[OPR1]; ROP_.NODE[OPR2]); IF .TX LSS 8 THEN (IF RESREQ THEN IF NOT .NODE[COPIED] THEN NODE[REGF]_TX_GETTN()) ELSE BEGIN MAP GTVEC TX; IF .TX[REQD] EQL MEMREQDB THEN IF .TX[REGF] EQL .ROP[ADDRF] THEN TX_0 END; IF NOT RESREQ THEN TX_0; IF .NODE[TPATH] THEN TEMP_TLA(.ROP,.TX,0); TLA(.LOP,0,0); IF NOT .NODE[TPATH] THEN TEMP_TLA(.ROP,.TX,0); WANTPREF(.NODE[REGF],.TEMP); IF .TX EQL 0 THEN TRYSIMPLESTORE(.NODE,.LOP,.ROP); .TX END)); MACRO INITPARMDESC=(LNKGD_.LNAME[LNKGDESCF]; PARMNO_0)$, NEXTPARMDESC= BEGIN IF (PARMNO_.PARMNO+1) GTR .LNKGD[LNKGSIZEF] THEN PT_STACKPARM ELSE (PT_.LNKGD[PARMTYPE(.PARMNO)]; PL_.LNKGD[PARMLOC(.PARMNO)]) END$; ROUTINE SPANPARMS= BEGIN LOCAL GTVEC T; DECR I FROM .CALLSTK[CURD] TO 0 DO FORALLTN(T,CALLSTK[LSELEM(.I)], (IF .T[LONLU] LSS .LON THEN T[LONLU]_.LON; IF .T[FONLU] LSS .FON THEN T[FONLU]_.FON)); NOVALUE END; MACRO INITCALL=INITSTK(CALLSTK)$, PUSHCALL=PUSHSTK(CALLSTK)$, NOTECALL=ADDTOTOS(CALLSTK,TNREP(.SUBNODE[REGF]))$, POPCALL=POPSTK(CALLSTK)$, RELEASECALL=RELEASESPACE(GT,.CALLSTK,STKSIZE)$; TLRDEF(CALL,( BEGIN BIND STVEC LNAME=NODE[OPR1]; LOCAL GTVEC SUBNODE:TN:LNKGD, OLON,OFON,N,PARMNO,PT,PL,FSP,Z; ! 1ST, BIND THE ROUTINE NAME TLA(.NODE[OPR2],0,0); INITPARMDESC; FSP_1; IF .NODE[NODESIZEF] GTR 2 THEN BEGIN PUSHCALL; INCR I FROM 2 TO .NODE[NODESIZEF]-1 DO BEGIN NEXTPARMDESC; SUBNODE_.NODE[OPERAND(.I)]; OLON_.LON+1; OFON_.FON+1; TN_TLA(.SUBNODE,0,0); SPAN(.SUBNODE,0); NOTECALL; SPANPARMS(); CASE .PT OF SET %0: STACK PARM % BEGIN IF .FSP THEN BEGIN LOCAL D; FSP_0; D_.DTDSTK[LDTD]; N_.DTEMPS[CURD]; SAVDTD; IF ((.DTEMPS[CURD] NEQ .D) OR (.NODE[NODESIZEF] EQL 3) OR (.NODE[NODESIZEF] EQL 5)) THEN IF TRYSPDYTEMP(.TN,.N) THEN EXITCASE (TN[REQD]_MEMREQDB) END; IF NOT TRYSPDYTEMP(.TN,N_.N+1) THEN OPENDYTEMP(.TN,.OLON,.OFON); DTDSTK[LDTD]_.N; TN[REQD]_MEMREQDB END; %1: SPECIFIC REGISTER % BEGIN LOCAL LEXEME SUBSUB,TTN; SUBSUB_.SUBNODE[OPR1]; IF .SUBSUB[LTYPF] EQL GTTYP THEN (TTN_.GT[.SUBSUB,REGF]; IF .TTN GEQ 8 THEN TN[TNPERMIT]_.TTN); TNSRREQD(.TN,.PL); END; %2: (LITERAL) MEMORY % BEGIN TN[TNLITBIT]_TRUE; TN[TNLITLEX]_LITLEXEME(.PL); TN[REQD]_MEMREQDB END; %3: (NAMED) MEMORY % BEGIN TN[REGF]_.PL; TN[REQD]_MEMREQDB END TES; IF NOT .FSP THEN KILLPDTEMPS(.SUBNODE, (IF .DTEMPS[CURD] EQL .N OR .I EQL .NODE[NODESIZEF]-1 THEN .N ELSE .N+1)) END; POPCALL END; NOTEDTD; IF NOT .FSP THEN POPDTD; IF .DTEMPS[CURD] GEQ (STKSIZE-.MAXPARMS) THEN KILLDYTEMPS(.NODE); ! GET A NEW TN FOR THE VALUE OF THE CALL AND MAKE IT THE VALUE REGISTER IF .LNAME[LNKGTF] NEQ INTRRPTLNKGT THEN BEGIN NODE[REGF]_TN_Z_GETTN(); IF .NODE[XOPR2] EQL .LXHALT THEN BINDSTORE(LITLEXEME(#177570),.TN) ELSE TNSRREQD(.TN,VREGNUM); END ELSE TN_Z_0; UPDATELONFON; SETBOUND; ASSIGNLABELS; SPAN(.NODE,0); SPAN(.NODE[OPR2],1); .Z END)); ROUTINE LOADR0(NODE)= BEGIN MAP GTVEC NODE; LOCAL GTVEC TX; NODE[REGF]_TX_GETTN(); TX[BNDTYP]_BNDREG; TX[REQD]_SRREQDB; TX[REGF]_VREGNUM; TX[BNDLSTHDR]_REGS[VREGNUM]; IF EMPTY(.REGS[VREGNUM]) THEN OPENREG(VREGNUM); .TX END; TLRDEF(ROUTINE,( BEGIN LOCAL STVEC RNAME:LNAME:LDESC, GTVEC TN:TL; RNAME_.NODE[OPR2]; RNAME[RETLAB]_.NODE; LDESC_.GT[LNAME_.RNAME[LNKGNMF],LNKGDESCF]; IF NOT .ANYENAB THEN BEGIN DECR I FROM 5 TO 0 DO NULLLST(REGS[.I]); INCR I FROM 1 TO .LDESC[LNKGSIZEF] DO IF .LDESC[PARMTYPE(.I)] EQL REGPARM THEN OPENREG(.LDESC[PARMLOC(.I)]); END; IF NOT EMPTY(.RNAME[REGFORMLST]) THEN BEGIN LOCAL LSTHDR L,ITEM I; I_L_.RNAME[REGFORMLST]; UNTIL (I_.I[RLINK]) EQL .L DO BEGIN TL_GETTN(); TL[BNDLSTHDR]_REGS[.I[LDATITEM(1)]]; TL[REQD]_MEMREQDB; TL[REGF]_.I[LDATITEM(1)]; WANTPREF(.TL,.GT[.I[RDATITEM(1)],REGF]); UPDATE(.I[RDATITEM(1)],1,2) END END; IF .LNAME[LNKGTF] NEQ INTRRPTLNKGT THEN TN_LOADR0(.NODE) ELSE TN_0; TL_TLA(.NODE[OPR1],0,0); UPDATELONFON; SPANUNARY(.NODE); WANTPREF(.TL,.TN); NODE[REGF]_.TN END)); NDRDEF(AND,( BEGIN LOCAL LOP,ROP,OP1,L; BIND TEMP=LABS; BIND LEXEME LEX2=NODE[OPR2]; L_LABELWORD(.NODE[OPR2],.LABS[LFF]); IF .LEX2[LTYPF] EQL LITTYP THEN IF LITVALUE(.LEX2) THEN L_.LABS ELSE L_LABELWORD(.LABS[LFF],.LABS[LFF]); LOP_ROP_0; IF .NODE[TPATH] THEN (ROP_.TX;OP1_.NODE[OPR2]) ELSE (LOP_.TX;OP1_.NODE[OPR1]); LOP_TLA(.NODE[OPR1],.LOP,.L); IF FLOWRES THEN SAVDTD; ROP_TLA(.NODE[OPR2],.ROP,.LABS); IF .NODE[TPATH] THEN LOP_.ROP; IF FLOWRES THEN BEGIN IF .DTEMPS[CURD] NEQ .DTDSTK[LDTD] THEN (KILLDYTEMPS(.NODE[OPR2]); SETNOTFPARM); POPDTD; RETURN 0; END; IF NOT RESREQ THEN RETURN .LOP; TEMP_0; IF .TX EQL 0 THEN IF ISDESTROYABLE(OP1) THEN TX_.LOP ELSE TEMP_.LOP; FILLTX; WANTPREF(.TX,.TEMP); .TX END)); NDRDEF(OR,( BEGIN LOCAL LOP,ROP,OP1,L; BIND TEMP=LABS; BIND LEXEME LEX2=NODE[OPR2]; L_LABELWORD(.LABS[LTF],.NODE[OPR2]); IF .LEX2[LTYPF] EQL LITTYP THEN IF LITVALUE(.LEX2) THEN L_LABELWORD(.LABS[LTF],.LABS[LTF]) ELSE L_.LABS; LOP_ROP_0; IF .NODE[TPATH] THEN (ROP_.TX;OP1_.NODE[OPR2]) ELSE (LOP_.TX;OP1_.NODE[OPR1]); LOP_TLA(.NODE[OPR1],.LOP,.L); IF FLOWRES THEN SAVDTD; ROP_TLA(.NODE[OPR2],.ROP,.LABS); IF .NODE[TPATH] THEN LOP_.ROP; IF FLOWRES THEN BEGIN IF .DTEMPS[CURD] NEQ .DTDSTK[LDTD] THEN (KILLDYTEMPS(.NODE[OPR2]); SETNOTFPARM); POPDTD; RETURN 0; END; IF NOT RESREQ THEN RETURN .LOP; TEMP_0; IF .TX EQL 0 THEN IF ISDESTROYABLE(OP1) THEN TX_.LOP ELSE TEMP_.LOP; FILLTX; WANTPREF(.TX,.TEMP); .TX END)); TLRDEF(NOT,TLCOMMON(.NODE,.TX,LABELWORD(.LABS[LFF],.LABS[LTF]))); NDRDEF(COMP,( BEGIN INCR I FROM 0 TO .NODE[NODESIZEF]-2 DO TLA(.NODE[OPERAND(.I)],0,0); TX_TLA(.NODE[LASTOPERAND],.TX,.LABS); IF RESREQ THEN .TX ELSE 0 END)); NDRDEF(IF,( BEGIN LOCAL DTUNEVEN,TT3,TT4, GTVEC TTHEN:TELSE; BINDLST(.NODE[OPR1]); TLA(.NODE[OPR2],0,LABELWORD(.NODE[OPR3],.NODE[OPR4])); SAVFON; SAVDTD; IF RESREQ THEN FILLTX; TTHEN_.NODE[OPR3]; TT3_(.TTHEN[CSCOMPL] LEQ MAGIC3); TELSE_.NODE[OPR4]; TT4_(.TELSE[CSCOMPL] LEQ MAGIC3); TTHEN_TLA(.TTHEN,IF .TT3 AND .TT4 THEN .TX,.LABS); RESETFON; RESETDTD; TELSE_TLA(.TELSE,IF .TT4 THEN .TX,.LABS); MAXFON; DTUNEVEN_(.DTEMPS[CURD] NEQ .DTDSTK[MDTD]); MINDTD; IF .DTUNEVEN THEN BEGIN KILLFORKDYTEMPS(.NODE[OPR3]); KILLFORKDYTEMPS(.NODE[OPR4]); SETNOTFPARM END; POPDTD; IF RESREQ THEN (WANTPREF(.TX,.TTHEN); WANTPREF(.TX,.TELSE)); BINDLST(.NODE[OPR5]); .TX END)); NDRDEF(CASE,( BEGIN LOCAL T,RES,DTUNEVEN,GTVEC SUBNODE; DTUNEVEN_0; BINDLST(.NODE[OPR1]); TLA(.NODE[OPR2],0,0); IF (RES_RESREQ) THEN FILLTX ELSE TX_0; SAVFON; SAVDTD; INCR I FROM 2 TO .NODE[NODESIZEF]-2 DO BEGIN SUBNODE_.NODE[OPERAND(.I)]; T_TLA(.SUBNODE,0,.LABS); IF .RES THEN WANTPREF(.T,.TX); IF .I GEQ 3 THEN IF .DTEMPS[CURD] NEQ .DTDSTK[MDTD] THEN DTUNEVEN_1; IF .I NEQ .NODE[NODESIZEF]-2 THEN RESETDTD ELSE MINDTD; RESETFON END; IF .DTUNEVEN THEN BEGIN INCR I FROM 2 TO .NODE[NODESIZEF]-2 DO KILLFORKDYTEMPS(.NODE[OPERAND(.I)]); SETNOTFPARM END; POPDTD; MAXFON; BINDLST(.NODE[OPERAND(.NODE[NODESIZEF]-1)]); .TX END)); ROUTINE FLOOP(NODE,TX,LABS,TYPE)= BEGIN ! TLA FOR WHILE-DO, UNTIL-DO, DO-WHILE, AND DO-UNTIL ! CASES 0 THROUGH 3 OF TYPE MAP GTVEC NODE, TNWORD TX:LABS; LOCAL L1,L2; LPBINDLST(.NODE[OPR1]); LPBINDLST(.NODE[OPR2]); L1_CASE .TYPE OF SET %WD% LABELWORD(.NODE[OPR4],.NODE[OPR5]); %UD% LABELWORD(.NODE[OPR5],.NODE[OPR4]); %DW% 0; %DU% 0 TES; L2_CASE .TYPE OF SET %WD% 0; %UD% 0; %DW% LABELWORD(.NODE[OPR3],.NODE[OPR5]); %DU% LABELWORD(.NODE[OPR5],.NODE[OPR3]) TES; SAVDTD; ENTLOOP(); TLA(.NODE[OPR3],0,.L1); IF (NOT .TYPE^(-1)) OR (BIND LEXEME OP4=NODE[OPR4]; IF .OP4[LTYPF] NEQ GTTYP THEN TRUE ELSE IF .GT[.OP4,NSRFF] EQL RFFLOW THEN TRUE ELSE ISRELOP(OP4) ) THEN (RESETDTD; KILLDYTEMPS(.NODE[OPR3])); TLA(.NODE[OPR4],0,.L2); RESETDTD; XITLOOP(); KILLDYTEMPS(.NODE[OPR4]); KILLDYTEMPS(.NODE); POPDTD; IF TNNEEDED THEN FILLTX; .TX END; NDRDEF(WD,FLOOP(.NODE,.TX,.LABS,0)); NDRDEF(UD,FLOOP(.NODE,.TX,.LABS,1)); NDRDEF(DW,FLOOP(.NODE,.TX,.LABS,2)); NDRDEF(DU,FLOOP(.NODE,.TX,.LABS,3)); NDRDEF(IDLOOP,( BEGIN LOCAL L, GTVEC CV; L_TLA(.NODE[OPR2],0,0); TLA(.NODE[OPR3],0,0); TLA(.NODE[OPR4],0,0); LPBINDLST(.NODE[OPR5]); LPBINDLST(.NODE[OPR6]); SPAN(.NODE[OPR2],0); NEXTLON; NEXTFON; SPAN(.NODE[OPR1],0); CV_.NODE[OPR1]; WANTPREF(.L,.CV[REGF]); SAVDTD; ENTLOOP(); TLA(.NODE[OPR7],0,0); RESETDTD; XITLOOP(); KILLDYTEMPS(.NODE[OPR7]); POPDTD; IF TNNEEDED THEN FILLTX; .TX END)); TLRDEF(LABEL,( BEGIN IF RESREQ THEN (IF .TX LSS 8 THEN TX_GETTN()) ELSE TX_0; NODE[REGF]_.TX; WANTPREF(TLCOMMON(.NODE,0,.LABS),.TX); KILLPDTEMPS(.NODE,.DTEMPS[CURD]); SETNOTFPARM; .TX END)); TLRDEF(LEAVE,( BEGIN LOCAL GTVEC N; N_.ST[.NODE[OPR2],LINKFLD]; TX_TLA(.NODE[OPR1],0,.LABS); WANTPREF(.N[REGF],.TX); NOTEDTD; .TX END)); TLRDEF(RLEAVE,( BEGIN LOCAL GTVEC RNTN; ! SWAP(LON,RLON); SWAP(FON,RFON); RNTN_.NODE[OPR2]; RNTN_.RNTN[RETLAB]; WANTPREF(TLA(.NODE[OPR1],0,.LABS),.RNTN[REGF]); NOTEDTD; UPDATELONFON; ! SWAP(LON,RLON); SWAP(FON,RFON); NODE[REGF]_0 END)); TLRDEF(SYNNULL,( BEGIN LOCAL GTVEC PAR; PAR_.NODE[CSPARENT]; IF NOT .PAR[BOUND] THEN (IF NOT .PAR[DELAYED] THEN NONBOGUS(PAR); IF .PAR NEQ .NODE THEN TLLIST(FASTLEXOUT(GTTYP,.PAR),0)); NOTEDTD; UPDATELONFON; ASSIGNLABELS; SPAN(.NODE,0); .NODE[REGF] END)); NDRDEF(SELECT,( BEGIN MAP GTVEC TX; LOCAL OTHEREND,DTUNEVEN,SAVDTC, LEXEME L, GTVEC OTHERTN; DTUNEVEN_0; IF RESREQ THEN FILLTX ELSE TX_0; INITTNSPAN(TX); OTHEREND_LITVALUE(.NODE[LASTOPERAND]); IF .OTHEREND EQL 0 THEN OTHERTN_0 ELSE NODE[OPERAND(.NODE[NODESIZEF]-2)]_LEXOUT(TNTYP,OTHERTN_GETTN()); TLA(.NODE[OPR1],0,0); INITTNSPAN(OTHERTN); INCR I FROM 1 TO .NODE[NODESIZEF]-3 DO BEGIN L_.NODE[OPERAND(.I)]; IF .I THEN !LEFT PART (IF .L[LTYPF] NEQ SELTYP THEN (TLA(.L,0,0);SPAN(.NODE[OPR1],0))) ELSE !RIGHT PART BEGIN IF .I EQL 2 THEN SAVDTC_.DTEMPS[CURD]; SAVDTD; TLA(.L,.TX,0); IF .DTEMPS[CURD] NEQ .SAVDTC THEN DTUNEVEN_1; RESETDTD; KILLDYTEMPS(.L); POPDTD; END; IF .I LEQ .OTHEREND THEN TNSPAN(OTHERTN) END; IF .OTHERTN NEQ 0 THEN IF (L_.OTHERTN[FONLU]-.OTHERTN[FONFU]) GTR .MAXFONSPAN THEN MAXFONSPAN_.L; IF .DTUNEVEN THEN SETNOTFPARM ELSE INCR I FROM 2 TO .NODE[NODESIZEF]-3 BY 2 DO BEGIN LOCAL LEXEME OP; BIND GTVEC SUBNODE=OP; OP_.NODE[OPERAND(.I)]; IF .OP[LTYPF] EQL GTTYP THEN SUBNODE[DTDELETE]_DTDONTCARE END; .TX END)); TLRDEF(ENABLE,( BEGIN SETBOUND; LOADR0(.NODE); NOTEDTD; UPDATELONFON; SPANUX(.NODE); TLA(.NODE[OPR1],0,0); .NODE[REGF] END)); NDRDEF(SIGNAL,( BEGIN LOCAL GTVEC TL; MAP GTVEC TX; TL_TLA(.NODE[OPR1],0,0); TX_LOADR0(.NODE); TX[REQD]_IGREQDB; WANTPREF(.TL,.TX); .TX END)); ! C. - DRIVER FOR TEMP NAME/LABEL ASSIGNMENT ! ------------------------------------------------ ! ! ! THIS PLIT IS USED TO SWITCH TO SPECIFIC ROUTINES TO DO ! TLA PROCESSING FOR A NODE, NODE-SPECIFIC PROCESSING FOR ! NODES WHICH USE TLCOMMON AS THEIR TLA ROUTINE, AND ! SPANNING FOR NODES WHICH USE TLCOMMON. ! ! BIND TLAR=0, !INDEX FOR NODE'S TLA ROUTINE NODER=1, !INDEX FOR "COMMON" NODE'S NODE-SPECIFIC ROUTINE SPANR=2; !INDEX FOR "COMMON" NODE'S SPAN ROUTINE STRUCTURE TNSWITCH[I,J]= (.TNSWITCH+3*.J+.I)<0,18>; BIND TNSWITCH TLPLIT=PLIT( TLCOMMON, NDADDSUB, SPANBINARY, ! + TLCOMMON, NDSWAB, SPANUNARY, ! SWAB TLCOMMON, NDB, SPANBINARY, ! / TLDOT, 0, 0, ! . TLCOMMON, NDADDSUB, SPANBINARY, ! - (BINARY) TLCOMMON, NDB, SPANBINARY, ! MOD TLCOMMON, NDB, SPANBINARY, ! * TLCOMMON, NDU, SPANUNARY, ! - (UNARY) TLCOMMON, NDLOADNODE, SPANLOADNODE, ! + (UNARY) TLCOMMON, NDB, SPANBINARY, ! ^ TLCOMMON, NDREL, SPANBXNARY, ! BIT TLCOMMON, NDREL, SPANBXNARY, ! GTR TLCOMMON, NDREL, SPANBXNARY, ! LEQ TLCOMMON, NDREL, SPANBXNARY, ! LSS TLCOMMON, NDREL, SPANBXNARY, ! GEQ TLCOMMON, NDREL, SPANBXNARY, ! EQL TLCOMMON, NDREL, SPANBXNARY, ! NEQ TLNOT, NDU, SPANUNARY, ! NOT TLCOMMON, NDB, SPANBINARY, ! EQV TLCOMMON, NDAND, AOSPAN, ! AND TLCOMMON, NDOR, AOSPAN, ! OR TLCOMMON, NDB, SPANBINARY, ! XOR 0, 0, 0, ! FADR 0, 0, 0, ! FDVR 0, 0, 0, ! FIX 0, 0, 0, ! FLOAT 0, 0, 0, ! FMPR 0, 0, 0, ! FNEG 0, 0, 0, ! FSBR TLCOMMON, NDREL, SPANBXNARY, ! GTRU TLCOMMON, NDREL, SPANBXNARY, ! LEQU TLCOMMON, NDREL, SPANBXNARY, ! LSSU TLCOMMON, NDREL, SPANBXNARY, ! GEQU TLCOMMON, NDREL, SPANBXNARY, ! EQLU TLCOMMON, NDREL, SPANBXNARY, ! NEQU TLCOMMON, NDB, SPANBINARY, ! ROT TLCOMMON, NDB, SPANBINARY, ! MAX TLCOMMON, NDB, SPANBINARY, ! MIN TLCOMMON, PUNT, SPANUNARY, ! CARRY TLCOMMON, PUNT, SPANUNARY, ! OVERFLOW TLCOMMON, NDSTORE, SPANSTORE, ! _ 0, 0, 0, ! ERROR OPERATOR TLCOMMON, NDCASE, SPANUX, ! CASE TLCOMMON, NDFSTO, SPANUX, ! CALL-PARM TLCOMMON, NDFSTO, SPANUX, ! CALL-STORE TLCOMMON, NDWD, SPANUX, ! WHILE-DO TLCOMMON, NDUD, SPANUX, ! UNTIL-DO TLROUTINE, 0, 0, ! ROUTINE DEFN TLCOMMON, NDCOMP, SPANUX, ! COMPOUND TLCOMMON, NDIDLOOP, SPANID, ! INCR TLCOMMON, NDIDLOOP, SPANID, ! DECR TLCOMMON, NDIF, SPANUX, ! IF TLCOMMON, NDDW, SPANUX, ! D0-WHILE TLCOMMON, NDDU, SPANUX, ! DO-UNTIL 0, 0, 0, ! CREATE 0, 0, 0, ! EXCHJ TLCOMMON, NDSELECT, SPANUX, ! SELECT 0, 0, 0, ! EXITLOOP TLLABEL, NDU, SPANUNARY, ! LABEL PLACEMENT 0, 0, 0, ! MODULE 0, 0, 0, ! PLIT TLCALL, 0, 0, ! CALL TLDOT, 0, 0, ! POINTER 0, 0, 0, ! [ TLLEAVE, 0, 0, ! LEAVE TLRLEAVE, 0, 0, ! RETURN TLSYNNULL, 0, 0, ! NULL TLNULL, 0, 0, ! INLINE TLENABLE, 0, 0, ! ENABLE TLCOMMON, NDSIGNAL, SPANUNARY, ! SIGNAL TLCOMMON, NDU, SPANUXNARY, ! MFPI, ETC. 0,0,0,0,0,0); TLRDEF(COMMON,( BEGIN ! ! THIS IS THE COMMON ROUTINE WHICH PERFORMS TN ASSIGNMENT ! FOR MOST BINARY (ARITHMETIC) OPERATORS. ! LOCAL TN,LOP,ROP,TEMP; IF ISCSEUSE(NODE) THEN BEGIN LOCAL GTVEC PAR; PAR_.NODE[CSPARENT]; IF NOT .PAR[BOUND] THEN (IF NOT .PAR[DELAYED] THEN NONBOGUS(PAR); IF .PAR NEQ .NODE THEN TLLIST(FASTLEXOUT(GTTYP,.PAR),0) ) END ELSE IF NOT .NODE[BOUND] THEN BEGIN SETBOUND; IF (TN_.NODE[REGF]) LSS 8 THEN TN_0; IF .TN EQL 0 THEN IF NOT ISCSECREATION(NODE) THEN TN_.TX[TNF]; TN_(.TLPLIT[NODER,.NODE[NODEX]])(.NODE,.TN,.LABS); IF .NODE[REGF] EQL 0 THEN NODE[REGF]_.TN; IF ISCSECREATION(NODE) THEN BINDUSES(.NODE) END; NOTEDTD; UPDATELONFON; ASSIGNLABELS; (.TLPLIT[SPANR,.NODE[NODEX]])(.NODE); .NODE[REGF] END)); ROUTINE TLA(NODE,TN,LABS)= BEGIN ! THIS ROUTINE IS THE COMMON DRIVER THROUGH WHICH ALL ! TEMP-LABEL-ASSIGNMENT ROUTINES ARE CALLED. ! MAP GTVEC NODE; BIND LEXEME LEX=NODE; IF .LEX[LTYPF] EQL LITTYP THEN RETURN 0; IF ONEOF(.NODE[TYPEF],BIT3(LOCALT,REGT,FORMALT)) THEN IF .NODE[REGF] GTR 7 THEN RETURN .NODE[REGF]; IF .NODE[TYPEF] NEQ GRAPHT THEN RETURN 0; TN_(.TLPLIT[TLAR,.NODE[NODEX]])(.NODE,.TN,.LABS); KOST(.NODE); NODE[LABELF]_0; .TN END; ! II.(A) ESTIMATING NUMBER OF TEMPS NEEDED ! ----------------------------------------- ! ! ! THIS CODE DOES A LINEAR SCAN OVER THE (UNRANKED) TEMP NAMES AND ! ATTEMPS TO GET A ROUGH ESTIMATE OF THE NUMBER OF ACTUAL TEMP ! LOCATIONS THAT WILL BE REQUIRED. ! ! ROUTINE ESTIMATE= BEGIN MACRO UPMD= (MD_.MD+1)$, SETFU= FU_.T[LONFU]$, SETLU= LU_.T[LONLU]$, SETBOTH=(SETFU;SETLU)$, NEWNEST=(IF .MD GTR .MDS THEN MDS_.MD;MD_1;SETBOTH)$, TFU= .T[LONFU]$, TLU= .T[LONLU]$, C1= NEWNEST$, C2= (UPMD;SETLU)$, C3= (UPMD;SETBOTH)$, C4= (UPMD;SETFU)$, C5= NEWNEST$, C6= UPMD$; LOCAL MD,MDS; REGISTER TNREPR R, GTVEC T; LOCAL FU,LU; MD_MDS_0; LU_0; FU_#777777; R_TNCHAIN<0,0>; WHILE (R_.R[LLINK]) NEQ TNCHAIN<0,0> DO BEGIN DUMMYBLOCK; T_.R[TNPTR]; IF TFU GEQ TLU THEN CONTINUE; IF ONEOF(.T[REQD],BIT3(MEMREQDB,SLREQDB,IGREQDB)) THEN CONTINUE; IF TFU LSS .FU THEN (IF TLU LSS .FU THEN C1 ELSE IF TLU GTR .LU THEN C6 ELSE C2) ELSE IF TFU GTR .LU THEN C5 ELSE IF TLU LSS .LU THEN C3 ELSE C4; END; IF .MD GTR .MDS THEN .MD ELSE .MDS END; ! III. - RANKING TEMP NAMES ! ------------------------------------------------ ! ! ! THE ACTION OF RANKING IS STRAIGHT-FORWARD AND SHOULD ! PRESENT NO PROBLEMS. NOTE, HOWEVER: ! ! 1) RANKING IS BASED ON THE 'MAX' COST -- THIS IS DONE ! SO THAT THE WORST CASE COST IS MINIMIZED. ! ! 2) CERTAIN TN'S MUST BE IN A REGISTER, OR IN A SPECIFIC ! REGISTER, IN A LOCAL, ETC. THESE TN'S ARE SEGREGATED ! ONTO SEPERATE LISTS AT THIS POINT. IN THE PACKING ! ALGORITHM THESE TN'S ARE TREATED FIRST IN ORDER ! TO INSURE THAT THEIR NEEDS ARE SATISFIED. ! ! ! A. - UTILITIES ! ------------------------------------------------ MACRO INITRANK= BEGIN MAXFONSPAN_LOG2(.MAXFONSPAN); NULLLST(SRLST); NULLLST(ARLST); NULLLST(SLLST); DECR I FROM ULSZ-1 TO 0 DO NULLLST(ULST[.I]) END$; ! B. - SORTING OF TEMP NAMES ! ------------------------------------------------ ROUTINE TNSORTENTER(TN)= BEGIN MAP GTVEC TN; MACRO KXY=.TN[XUSECOMPLEXITY]$, FS=(.MAXFONSPAN-LOG2(.TN[FONLU]-.TN[FONFU])+1)$, SZ=ULSZ$, MAX=(.MAXKOST*(.MAXFONSPAN+1)+1)$; LOCAL GTVEC T, TNLSTHDR L; LOCAL LCOST,LMAX; LCOST_(KXY*FS)*SZ; LMAX_MAX; TN[USECOMPLEXITY]_.TN[XUSECOMPLEXITY]-.TN[USECOMPLEXITY]; L_.ULST[.LCOST/.LMAX]; TN[XUSECOMPLEXITY]_.LCOST MOD .LMAX; FORALLTN(T,L, IF .T[XUSECOMPLEXITY] LSS .TN[XUSECOMPLEXITY] THEN RETURN LINK(TNREP(.TN),.TR[LLINK])); LINK(TNREP(.TN),.L[LLINK]) END; ROUTINE LONORDER(TN,L)= BEGIN MAP GTVEC TN, TNLSTHDR L; LOCAL GTVEC T,TNREPR TF; L_@.L; TF_TNREP(.TN); IF .TN[LONFU] NEQ .TN[FONFU] THEN RETURN LINK(.TF,.L[RLINK]); FORALLTN(T,L, IF .T[LONFU] EQL .T[FONFU] THEN IF .T[LONFU] GTR .TN[LONFU] THEN RETURN LINK(.TF,.TR[LLINK])); LINK(.TF,.L[LLINK]) END; ! C. - DRIVER FOR RANKING ! ------------------------------------------------ ROUTINE TRANK= BEGIN LOCAL GTVEC T; INITRANK; FORALLTN(T,TNCHAIN, BEGIN IF .T[LONFU] LEQ .T[LONLU] THEN CASE .T[REQD] OF SET % 0 % TNSORTENTER(.T); ! USUAL CASE % 1 % 0; ! ALREADY BOUND % 2 % LONORDER(.T,SLLST); ! MUST BE STATIC LOCAL (ADDR USED) % 3 % LINK(TNREP(.T),ARLST); ! ANY REGISTER % 4 % LINK(TNREP(.T),SRLST); ! SPECIFIC REGISTER % 5 % 0; ! IGNORE DUMMY ENTRIES % 6 % TNSORTENTER(.T); ! DECLARED LOCALS % 7 % TNSORTENTER(.T) ! REGISTER OR FORGET IT TES END); NOVALUE END; ! IV. - PACKING ! ------------------------------------------------ ! ! ! THIS, THE LAST PHASE, TAKES THE ORDERED LIST OF TN'S ! AND ATTEMPTS A 'BEST-FIT' PACKING INTO THE AVAILABLE ! REGISTERS, LOCALS, ETC. THE UTILITIES DEFINE VARIOUS ! PRIMITIVES. THE MAIN WORK, AND THE IMPLEMENTATION ! OF THE PACKING POLICY, IS CONTAINED IN THE ROUTINE 'TPACK'. ! ! ! A. - UTILITIES ! ------------------------------------------------ ! 0. - REPACKING (ALREADY!) REQUIRE RESHUF.RTN; ! 1. - PREFERENCES ! ! IN A FEW CASES WE 'PREFER' THAT TWO TEMP NAMES ! BE PACKED INTO THE SAME LOCATION. THIS SECTION ! PROVIDES THE MECHANISM FOR DOING THIS. THE 'TL' ! ROUTINES ARE CHARGED WITH THE RESPONSIBILITY ! OF NOTING THAT SUCH BINDING IS DESIRABLE. ! MACRO INITPREF=PREFLST_0$, PRFLST=1,1,0,18$, PRFTHREAD=1,1,18,18$; ROUTINE PREFLINK(T)= BEGIN ! PUT A PREFREP ON THE PREFCHAIN MAP GTVEC T; LOCAL TNREPR TR; TR_T[PREFF]_TNREP(.T); TR[PRFTHREAD]_.PREFLST[BASE]; PREFLST[BASE]_.TR END; ROUTINE WANTPREF(T,TW)= BEGIN MAP GTVEC T:TW; LOCAL TNREPR P:P1; IF .TW LSS 8 THEN RETURN; IF .T LSS 8 THEN RETURN; IF .T EQL .TW THEN RETURN; IF (P_.TW[PREFF]) EQL 0 THEN P_PREFLINK(.TW); IF (P1_.T[PREFF]) EQL 0 THEN P1_PREFLINK(.T); LINK(.P,.P1) END; ROUTINE TRYPREF(TN)= BEGIN MAP GTVEC TN; MACRO OK=(TN[REGF]_.T; TN[REQD]_MEMREQDB; TN[BNDTYP]_BNDPREF; SUCCESS)$; LOCAL OPENED,TRIED,REG,TEMP,GTVEC T; IF .TN[PREFF] NEQ 0 THEN BEGIN FORALLTN(T,.TN[PREFF], (BEGIN IF ISREGLST(REG_.T[BNDLSTHDR]) THEN IF TRYFIT(.TN,.REG) THEN OK ELSE IF SLOW THEN BEGIN LOCAL C[SRCHWIDTH],CNT; TEMP_.T[REQD];T[REQD]_SRREQDB; IF (CNT_COUNTCONFLICTS(.TN,.REG,C)) LEQ SRCHWIDTH THEN IF TRYALT(.TN,.CNT,.REG,C,SRCHDEPTH) THEN (T[REQD]_.TEMP; OK); T[REQD]_.TEMP END END)); IF FAST THEN EXITCOMPOUND; OPENED_0; TRIED_.RESERVED; FORALLTN(T,.TN[PREFF], (BEGIN IF ISREGLST(REG_.T[BNDLSTHDR]) THEN IF NOT .TRIED<.REG-REGS<0,0>,1> THEN BEGIN LOCAL C[SRCHWIDTH],CNT; TRIED<.REG-REGS<0,0>,1>_1; TEMP_.T[REQD];T[REQD]_SRREQDB; IF (CNT_COUNTCONFLICTS(.TN,.REG,C)) LEQ SRCHWIDTH THEN BEGIN IF NOT .OPENED THEN INCR I FROM 0 TO 5 DO IF EMPTY(.REGS[.I]) THEN (OPENREG(.I); OPENED_1; EXITLOOP); IF NOT .OPENED THEN (T[REQD]_.TEMP; EXITLOOP); IF TRYALT(.TN,.CNT,.REG,C,SRCHDEPTH) THEN (T[REQD]_.TEMP; OK) END; T[REQD]_.TEMP END END)); IF .TN[REQD] EQL RFREQDB THEN FAIL; IF .TN[USECOMPLEXITY] GTR 6 THEN FAIL; FORALLTN(T,.TN[PREFF], (IF MUSTBETOP(.TN,.T[BNDLSTHDR]) THEN IF TRYFIT(.TN,.T[BNDLSTHDR]) THEN OK)); FORALLTN(T,.TN[PREFF], BEGIN IF .T[BNDLSTHDR] NEQ 0 THEN IF TRYFIT(.TN,.T[BNDLSTHDR]) THEN OK END); END; FAIL END; ! NOW LOOK AT TRY.BLI FOR THE REST OF THE "PACKING" ROUTINES ! E. - DRIVER FOR PACKING ! ------------------------------------------------ ! ! ! ! THE FOLLOWING ROUTINE, 'TPACK', DEFINES THE POLICY ! BY WHICH TEMP NAMES ARE BOUND TO LOCATIONS. THAT POLICY ! IS: ! ! 1) BIND THOSE TN'S WHICH MUST BE IN A SPECIFIC REGISTER. ! 2) BIND THOSE TN'S THAT MUST BE IN SOME REGISTER. ! 3) BIND THOSE TN'S THAT MUST BE IN SOME LOCAL. ! 4) BIND THE REMAINDER OF THE TN'S - IN ORDER OF THEIR IMPORTANCE -. ! ! WITHIN 4) THE ALGORITHM IS: ! ! 4A) TRY TO USE THE TN'S 'PREFERENCE', IF ANY. ! 4B) TRY AN OPEN REGISTER. ! 4C) IF THE DIFFERENCE BETWEEN THE TN'S MAX AND MIN COSTS ! IS SUFFICIENTLY SMALL, THEN TRY AN OPEN LOCAL. ! 4D) TRY A CLOSED REGISTER. ! 4E) IF THE DIFFERENCE BETWEEN THE TN'S MAX AND MIN COSTS ! PREVENTED THE ATTEMPT IN 4C), THEN TRY THE ! OPEN LOCALS NOW. ! 4F) USE A CLOSED LOCAL ( THIS WILL ALWAYS WORK AS ! A LAST RESORT). ! ! NOTE THAT THE TN-REP LISTS ARE RELEASED AS WE GO ! THROUGH ALL THIS. ! ! BIND NOTENUFREGS = 98; ! COPIED FROM ERROR.BEG EXTERNAL WARNEM; ROUTINE TPACK= BEGIN LOCAL GTVEC T; INITSTEMPS; FORALLTN(T,SRLST,TRYSPREG(.T,.T[REGF])); RELTNREPLST(SRLST); FORALLTN(T,ARLST, IF NOT TRYREGSEARCH(.T,SRCHDEPTH) THEN IF NOT(TRYCLREG(.T)) THEN (WARNEM (0,NOTENUFREGS); T[BNDLSTHDR]_REGS[5]<0,0>; MARKTN(T,BNDREG); T[REGF]_5)); RELTNREPLST(ARLST); IF .ESTIM GTR 1 THEN BEGIN IF .ESTIM GTR 6 THEN ESTIM_6; IF .ESTIM GTR 2 THEN ESTIM_.ESTIM-1; IF .DTDSTK[MAXD] GEQ 0 THEN ESTIM_.ESTIM-1; DECR I FROM 5 TO 0 DO (IF .RESERVED[.I,1] THEN OPENREG(.I) ELSE IF ISOPEN(.REGS[.I]) THEN ESTIM_.ESTIM-1); IF .ESTIM GTR 0 THEN INCR I FROM 0 TO 5 DO IF EMPTY(.REGS[.I]) THEN IF (ESTIM_.ESTIM-1) GEQ 0 THEN OPENREG(.I) ELSE EXITLOOP; END; DECR I FROM (ULSZ-1) TO 0 DO BEGIN FORALLTN(T,ULST[.I], BEGIN BEGIN DUMMYBLOCK; IF .T[PREFF] NEQ 0 THEN IF TRYPREF(.T) THEN CONTINUE; IF TRYREGSEARCH(.T,SRCHDEPTH) THEN CONTINUE; IF TRYCLREG(.T) THEN CONTINUE; IF .T[REQD] EQL RFREQDB THEN BEGIN T[REQD]_MEMREQDB; T[REGF]_.T[OFFSETF]; T[OFFSETF]_0; CONTINUE END; IF TRYDYTEMPS(.T) THEN CONTINUE; LONORDER(.T,SLLST) END; END); RELTNREPLST(ULST[.I]) END; FORALLTN(T,SLLST, IF NOT(TRYOPSTEMP(.T)) THEN TRYCLSTEMP(.T)); RELTNREPLST(SLLST); BEGIN MAP TNREPR T; REGISTER TEMP; T[BASE]_.PREFLST[BASE]; WHILE .T[BASE] NEQ 0 DO BEGIN TEMP_.T[PRFTHREAD]; RELTNREP(.T[BASE]); T[BASE]_.TEMP END END; NOVALUE END; ! F. - MARKING OF TNS AFTER PACKING ROUTINE TMARK= BEGIN MACRO CHKPREF=DUMMYBLOCK; IF .T[BNDTYP] EQL BNDPREF THEN CONTINUE$; LOCAL GTVEC T; DECR I FROM 5 TO 0 DO FORALLTN(T,REGS[.I],(CHKPREF; MARKTN(T,BNDREG); T[REGF]_.I)); STATICSIZE_(.STEMPS[MAXD]+1)*2; DECR I FROM .STEMPS[MAXD] TO 0 DO FORALLTN(T,STEMPS[LSELEM(.I)],(CHKPREF; MARKTN(T,BNDLOCAL); T[REGF]_SP; T[MODE]_INDEXED; T[OFFSETF]_-(.MAXLOCALS+(.I+1)*2))); DECR I FROM .DTEMPS[MAXD] TO 0 DO FORALLTN(T,DTEMPS[LSELEM(.I)], (CHKPREF; IF .T[BNDTYP] EQL 0 THEN MARKTN(T,BNDPUSH % USED TO BE BNDLOCAL -- BWL %); T[REGF]_SP; T[MODE]_INDEXED; T[OFFSETF]_-(.MAXLOCALS+.STATICSIZE+(.I+1)*2))); NOVALUE END; ROUTINE MARKSYMBOLS= BEGIN REGISTER STVEC STE; STE_.PURGED; UNTIL .STE EQL 0 DO BEGIN REGISTER REG,GTVEC NODE; SELECT .STE[TYPEF] OF NSET REGT: NODE_.STE; LOCALT: NODE_.STE; MBINDT: (NODE_.STE[BINDLEXF]; IF .NODE NEQ GTTYP THEN EXITBLOCK STE_.STE[THREAD]); OTHERWISE: EXITBLOCK STE_.STE[THREAD] TESN; UNTIL (REG_.NODE[REGF]) LEQ 7 DO (NODE_.REG); IF .REG EQL SP THEN STE[OFFSETF]_.NODE[OFFSETF]; STE[SREGF]_.REG; STE_.STE[THREAD] END; NOVALUE END; ! V. - DRIVER FOR TNBIND MODULE ROUTINE INITPDTNS= BEGIN MACRO MAKEREG(NAME,REGNUM,IGNORE)= BEGIN MAP GTVEC NAME; REGISTER GTVEC L; L_NAME[REGF]_GETTN(); L[REGF]_(REGNUM); IF IGNORE THEN L[REQD]_IGREQDB ELSE L[REQD]_SRREQDB; L[BNDTYP]_BNDREG; END$; BIND Z=0; MAKEREG(PCREG,PC,1); MAKEREG(SPREG,SP,1); MAKEREG(VVREG,VR,1); MAKEREG(RR0,0,0); MAKEREG(RR1,1,0); MAKEREG(RR2,2,0); MAKEREG(RR3,3,0); MAKEREG(RR4,4,0); MAKEREG(RR5,5,0); END; GLOBAL ROUTINE TNBIND(NODE)= BEGIN MAP GTVEC NODE; INITPDTNS(); INITPREF; INITDYTEMPS; INITLOOP; INITCALL; INITLS(FONSTK); INITLS(DTDSTK); IF (.NODE[NODEX] NEQ DCROUTINE) OR .ANYENAB THEN INITREGS; LON_FON_1; MAXFONSPAN_MAXKOST_0; SAVDTD; TLA(.NODE,0,0); POPDTD; RELEASELOOP; RELEASECALL; ESTIM_ESTIMATE(); TRANK(); TPACK(); TMARK(); IF .DEBFLG THEN MARKSYMBOLS(); NOVALUE END; END END ELUDOM